Skip to main content

grit_lib/hash/
mod.rs

1//! Incremental hashing for Git object ids and file checksums.
2//!
3//! Parallel batch helpers: [`hash_objects_parallel`], [`par_hash_with`], and [`Parallelism`].
4//!
5//! This module is the single owner of the `sha1`, `sha2`, and `sha1dc` crates in
6//! `grit-lib`.
7//!
8//! **Object ids** name Git objects. SHA-1 ids are computed with [`sha1dc`] (collision
9//! detection, standard digest mode). [`ObjectHasher::finalize`], [`hash_object`], and
10//! [`HashAlgo::digest`] return [`Result`] and surface [`crate::error::ObjectError::HashCollision`] on
11//! chosen-prefix collisions. Canonical store bytes are `"<kind> <len>\\0<payload>"`;
12//! use [`HashAlgo::digest`] when hashing raw bytes that should become an [`ObjectId`]
13//! (for example verifying loose object headers).
14//!
15//! **Checksums** detect corruption in pack, index, MIDX, commit-graph, and related
16//! file trailers. They use the same digest algorithms but are not object identities.
17//! Use [`ChecksumHasher`] / [`HashAlgo::checksum_digest`], [`HashingWriter`], and
18//! [`verify_trailer`].
19
20#![allow(dead_code)]
21
22use crate::error::ObjectError;
23use std::io::{self, Write};
24
25use sha1::{Digest as Sha1Digest, Sha1};
26use sha1dc::Hasher as Sha1dcHasher;
27use sha2::Sha256;
28
29use crate::error::{Error, Result};
30use crate::objects::{HashAlgo, ObjectId, ObjectKind};
31
32mod parallel;
33
34pub use parallel::{
35    hash_objects_parallel, par_hash_with, parallel_hash_worthwhile, try_par_hash_forced,
36    try_par_hash_with, ParallelHashError, Parallelism, PAR_HASH_MIN_ITEMS,
37    PAR_HASH_MIN_TOTAL_BYTES,
38};
39
40/// Which implementation the `sha1` / `sha2` dependency selects for `algo` on this CPU.
41///
42/// Values mirror the `cpufeatures` dispatch inside those crates for the digests
43/// Grit uses (SHA-1 and SHA-256). On x86_64, SHA-256 in `sha2` 0.11 only selects
44/// SHA-NI or portable code (AVX2 is used for SHA-512, not SHA-256, so there is no
45/// separate AVX2 backend variant here).
46#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
47pub enum Backend {
48    /// x86_64 SHA-NI (`sha` target feature) — used for SHA-1 and SHA-256 when available.
49    X86ShaNi,
50    /// AArch64 SHA2 crypto extensions.
51    Aarch64Sha,
52    /// Portable software implementation.
53    Portable,
54}
55
56impl Backend {
57    /// Stable lowercase name for scripts and JSON (`x86_sha_ni`, `portable`, …).
58    #[must_use]
59    pub const fn as_str(self) -> &'static str {
60        match self {
61            Self::X86ShaNi => "x86_sha_ni",
62            Self::Aarch64Sha => "aarch64_sha",
63            Self::Portable => "portable",
64        }
65    }
66}
67
68impl std::fmt::Display for Backend {
69    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
70        f.write_str(self.as_str())
71    }
72}
73
74/// Report the hashing backend used for object-id digests on this CPU.
75///
76/// SHA-1 object ids go through [`sha1dc`] (hardware SHA-1 when available). SHA-256
77/// uses the `sha2` crate. File checksums use plain accelerated SHA-1 from the `sha1`
78/// crate, not sha1dc.
79///
80/// Detection uses the same target features as those crates (`sha` on x86_64, `sha2` on
81/// AArch64). `algo` is accepted for a stable signature; both supported algorithms share
82/// the same backend on a given CPU.
83#[must_use]
84pub fn backend(algo: HashAlgo) -> Backend {
85    let _ = algo;
86    #[cfg(target_arch = "x86_64")]
87    {
88        if std::arch::is_x86_feature_detected!("sha") {
89            Backend::X86ShaNi
90        } else {
91            Backend::Portable
92        }
93    }
94    #[cfg(target_arch = "aarch64")]
95    {
96        if std::arch::is_aarch64_feature_detected!("sha2") {
97            Backend::Aarch64Sha
98        } else {
99            Backend::Portable
100        }
101    }
102    #[cfg(not(any(target_arch = "x86_64", target_arch = "aarch64")))]
103    {
104        Backend::Portable
105    }
106}
107/// Maximum length of a Git object header (`"<kind> <decimal-len>\\0"`) on the stack.
108///
109/// Longest kind name is `"commit"` (6 bytes) plus space, up to 20 decimal digits
110/// for the payload length, plus the trailing NUL.
111const OBJECT_HEADER_BUF_LEN: usize = 6 + 1 + 20 + 1;
112
113/// Incremental hasher for Git file checksums (pack/index/MIDX/commit-graph trailers).
114///
115/// Checksums use the same SHA-1 or SHA-256 digests as object ids but name file
116/// integrity, not [`ObjectId`] values. Prefer this type anywhere a trailer or
117/// non-object content hash is computed or verified.
118#[derive(Debug, Clone)]
119pub enum ChecksumHasher {
120    /// SHA-1 (20-byte digests).
121    Sha1(Sha1),
122    /// SHA-256 (32-byte digests).
123    Sha256(Sha256),
124}
125
126impl ChecksumHasher {
127    /// Create a fresh checksum hasher for `algo`.
128    #[must_use]
129    pub fn new(algo: HashAlgo) -> Self {
130        algo.checksum_hasher()
131    }
132
133    /// The hash algorithm this hasher produces.
134    #[must_use]
135    pub fn algo(self: &ChecksumHasher) -> HashAlgo {
136        match self {
137            Self::Sha1(_) => HashAlgo::Sha1,
138            Self::Sha256(_) => HashAlgo::Sha256,
139        }
140    }
141
142    /// Feed more bytes into the digest.
143    pub fn update(&mut self, data: &[u8]) {
144        match self {
145            Self::Sha1(h) => h.update(data),
146            Self::Sha256(h) => h.update(data),
147        }
148    }
149
150    /// Finish hashing and return the raw digest bytes.
151    #[must_use]
152    pub fn finalize(self) -> Vec<u8> {
153        match self {
154            Self::Sha1(h) => h.finalize().to_vec(),
155            Self::Sha256(h) => h.finalize().to_vec(),
156        }
157    }
158
159    /// Write the raw digest into `out` and return the number of bytes written.
160    ///
161    /// # Panics
162    ///
163    /// Panics when `out` is shorter than the digest length for this algorithm.
164    #[must_use]
165    pub fn finalize_into(self, out: &mut [u8]) -> usize {
166        let digest = self.finalize();
167        let len = digest.len();
168        assert!(
169            out.len() >= len,
170            "checksum digest buffer too short: need {len} bytes, have {}",
171            out.len()
172        );
173        out[..len].copy_from_slice(&digest);
174        len
175    }
176}
177
178impl Write for ChecksumHasher {
179    fn write(&mut self, buf: &[u8]) -> io::Result<usize> {
180        self.update(buf);
181        Ok(buf.len())
182    }
183
184    fn flush(&mut self) -> io::Result<()> {
185        Ok(())
186    }
187}
188
189/// Incremental hasher for Git's supported object-id algorithms.
190#[derive(Debug, Clone)]
191pub enum ObjectHasher {
192    /// SHA-1 (20-byte digests) with sha1dc collision detection.
193    Sha1(Sha1dcHasher),
194    /// SHA-256 (32-byte digests).
195    Sha256(Sha256),
196}
197
198impl ObjectHasher {
199    /// Create a fresh hasher for `algo`.
200    #[must_use]
201    pub fn new(algo: HashAlgo) -> Self {
202        algo.hasher()
203    }
204
205    /// The hash algorithm this hasher produces.
206    #[must_use]
207    pub fn algo(self: &ObjectHasher) -> HashAlgo {
208        match self {
209            Self::Sha1(_) => HashAlgo::Sha1,
210            Self::Sha256(_) => HashAlgo::Sha256,
211        }
212    }
213
214    /// Feed more bytes into the digest.
215    pub fn update(&mut self, data: &[u8]) {
216        match self {
217            Self::Sha1(h) => h.update(data),
218            Self::Sha256(h) => h.update(data),
219        }
220    }
221
222    /// Create a hasher that already consumed the Git object header for `kind` and `len`.
223    ///
224    /// The header is written into a stack buffer (no heap allocation).
225    #[must_use]
226    pub fn for_object(algo: HashAlgo, kind: ObjectKind, len: u64) -> Self {
227        let mut hasher = Self::new(algo);
228        let mut header = [0u8; OBJECT_HEADER_BUF_LEN];
229        let header_len = write_object_header(&mut header, kind, len);
230        hasher.update(&header[..header_len]);
231        hasher
232    }
233
234    /// Finish hashing and return the object id.
235    ///
236    /// # Errors
237    ///
238    /// Returns [`crate::error::ObjectError::HashCollision`] when sha1dc detects a chosen-prefix collision.
239    pub fn finalize(self) -> Result<ObjectId> {
240        match self {
241            Self::Sha1(h) => match h.finalize() {
242                Ok(digest) => Ok(object_id_from_sha1_digest(&digest)),
243                Err(collision) => Err(collision_to_error(collision)),
244            },
245            Self::Sha256(h) => Ok(ObjectId::from_bytes(h.finalize().as_slice())
246                .unwrap_or_else(|_| unreachable!("SHA-256 digest is 32 bytes"))),
247        }
248    }
249
250    /// Write the raw digest into `out` and return the number of bytes written.
251    ///
252    /// # Errors
253    ///
254    /// Returns [`crate::error::ObjectError::InvalidId`] when `out` is shorter than the digest
255    /// length for this algorithm (a diagnostic string names the required size).
256    pub fn finalize_into(self, out: &mut [u8]) -> Result<usize> {
257        match self {
258            Self::Sha1(h) => {
259                let oid = match h.finalize() {
260                    Ok(digest) => object_id_from_sha1_digest(&digest),
261                    Err(collision) => return Err(collision_to_error(collision)),
262                };
263                let bytes = oid.as_bytes();
264                if out.len() < bytes.len() {
265                    return Err(Error::Object(ObjectError::InvalidId {
266                        input: format!(
267                            "digest buffer too short: need {} bytes, have {}",
268                            bytes.len(),
269                            out.len()
270                        ),
271                    }));
272                }
273                out[..bytes.len()].copy_from_slice(bytes);
274                Ok(bytes.len())
275            }
276            Self::Sha256(h) => {
277                let digest = h.finalize();
278                let len = digest.len();
279                if out.len() < len {
280                    return Err(Error::Object(ObjectError::InvalidId {
281                        input: format!(
282                            "digest buffer too short: need {len} bytes, have {}",
283                            out.len()
284                        ),
285                    }));
286                }
287                out[..len].copy_from_slice(&digest);
288                Ok(len)
289            }
290        }
291    }
292}
293
294impl Write for ObjectHasher {
295    fn write(&mut self, buf: &[u8]) -> io::Result<usize> {
296        self.update(buf);
297        Ok(buf.len())
298    }
299
300    fn flush(&mut self) -> io::Result<()> {
301        Ok(())
302    }
303}
304
305impl HashAlgo {
306    /// Return a fresh incremental checksum hasher for this algorithm.
307    #[must_use]
308    pub fn checksum_hasher(self) -> ChecksumHasher {
309        match self {
310            Self::Sha1 => ChecksumHasher::Sha1(Sha1::new()),
311            Self::Sha256 => ChecksumHasher::Sha256(Sha256::new()),
312        }
313    }
314
315    /// Hash a byte slice with no Git object header and return a file checksum.
316    #[must_use]
317    pub fn checksum_digest(self, data: &[u8]) -> Vec<u8> {
318        let mut hasher = self.checksum_hasher();
319        hasher.update(data);
320        hasher.finalize()
321    }
322
323    /// Return a fresh incremental hasher for this algorithm.
324    #[must_use]
325    pub fn hasher(self) -> ObjectHasher {
326        match self {
327            Self::Sha1 => ObjectHasher::Sha1(Sha1dcHasher::new()),
328            Self::Sha256 => ObjectHasher::Sha256(Sha256::new()),
329        }
330    }
331
332    /// Hash a byte slice with no Git object header.
333    ///
334    /// # Errors
335    ///
336    /// Returns [`crate::error::ObjectError::HashCollision`] when sha1dc detects a chosen-prefix collision.
337    pub fn digest(self, data: &[u8]) -> Result<ObjectId> {
338        let mut hasher = self.hasher();
339        hasher.update(data);
340        hasher.finalize()
341    }
342
343    /// Hash canonical Git store bytes for `kind` and `data`.
344    ///
345    /// # Errors
346    ///
347    /// Returns [`crate::error::ObjectError::HashCollision`] when sha1dc detects a chosen-prefix collision.
348    pub fn hash_object(self, kind: ObjectKind, data: &[u8]) -> Result<ObjectId> {
349        hash_object(self, kind, data)
350    }
351}
352
353/// Hash canonical Git store bytes for `kind` and `data`.
354///
355/// Equivalent to [`HashAlgo::hash_object`] but accepts the algorithm as the
356/// first argument.
357///
358/// Detection runs over the bytes that form the object id (header and payload), as in
359/// Git. A payload that only collides when hashed on its own, such as the SHAttered
360/// PDFs stored as blobs in Git's own history, is an ordinary object.
361///
362/// # Errors
363///
364/// Returns [`crate::error::ObjectError::HashCollision`] when sha1dc detects a chosen-prefix collision.
365pub fn hash_object(algo: HashAlgo, kind: ObjectKind, data: &[u8]) -> Result<ObjectId> {
366    let len = u64::try_from(data.len()).unwrap_or(u64::MAX);
367    let mut hasher = ObjectHasher::for_object(algo, kind, len);
368    hasher.update(data);
369    hasher.finalize()
370}
371
372/// Incremental Git object-id hash (header plus payload chunks).
373///
374/// Use this instead of constructing [`ObjectHasher`] outside the hash module.
375pub struct ObjectPayloadHasher {
376    inner: ObjectHasher,
377}
378
379impl ObjectPayloadHasher {
380    /// Start hashing canonical store bytes for `kind` with payload length `len`.
381    #[must_use]
382    pub fn new(algo: HashAlgo, kind: ObjectKind, len: u64) -> Self {
383        Self {
384            inner: ObjectHasher::for_object(algo, kind, len),
385        }
386    }
387
388    /// Feed more decompressed payload bytes.
389    pub fn update(&mut self, chunk: &[u8]) {
390        self.inner.update(chunk);
391    }
392
393    /// Finish and return the object id.
394    ///
395    /// # Errors
396    ///
397    /// Returns [`crate::error::ObjectError::HashCollision`] when sha1dc detects a chosen-prefix collision.
398    pub fn finish(self) -> Result<ObjectId> {
399        self.inner.finalize()
400    }
401}
402
403fn object_id_from_sha1_digest(digest: &sha1dc::Digest) -> ObjectId {
404    ObjectId::from_bytes(digest.as_ref())
405        .unwrap_or_else(|_| unreachable!("SHA-1 digest is 20 bytes"))
406}
407
408fn collision_to_error(collision: sha1dc::Collision) -> Error {
409    Error::Object(ObjectError::HashCollision {
410        oid: object_id_from_sha1_digest(&collision.digest()),
411    })
412}
413
414/// A writer that forwards bytes to an inner sink while accumulating a checksum.
415///
416/// Call [`Self::finish`] to append the raw digest trailer to the inner writer
417/// and obtain the digest as an [`ObjectId`].
418pub struct HashingWriter<W: Write> {
419    inner: W,
420    hasher: ChecksumHasher,
421}
422
423impl<W: Write> HashingWriter<W> {
424    /// Wrap `inner`, hashing every byte written through this adapter.
425    #[must_use]
426    pub fn new(algo: HashAlgo, inner: W) -> Self {
427        Self {
428            inner,
429            hasher: algo.checksum_hasher(),
430        }
431    }
432
433    /// Borrow the inner writer without finishing the checksum.
434    #[must_use]
435    pub fn get_ref(&self) -> &W {
436        &self.inner
437    }
438
439    /// Mutably borrow the inner writer without finishing the checksum.
440    pub fn get_mut(&mut self) -> &mut W {
441        &mut self.inner
442    }
443
444    /// Append the checksum trailer to the inner writer and return it with the digest.
445    ///
446    /// # Errors
447    ///
448    /// Propagates I/O errors from writing the trailer to `inner`.
449    pub fn finish(mut self) -> io::Result<(W, ObjectId)> {
450        let digest_bytes = self.hasher.finalize();
451        self.inner.write_all(&digest_bytes)?;
452        let digest = ObjectId::from_bytes(&digest_bytes)
453            .unwrap_or_else(|_| unreachable!("checksum digest length matches object id for algo"));
454        Ok((self.inner, digest))
455    }
456}
457
458impl<W: Write> Write for HashingWriter<W> {
459    fn write(&mut self, buf: &[u8]) -> io::Result<usize> {
460        let n = self.inner.write(buf)?;
461        if n > 0 {
462            self.hasher.update(&buf[..n]);
463        }
464        Ok(n)
465    }
466
467    fn flush(&mut self) -> io::Result<()> {
468        self.inner.flush()
469    }
470}
471
472/// Checksum at the end of `bytes` did not match a digest of the leading body.
473#[derive(Debug, Clone, PartialEq, Eq)]
474pub struct TrailerMismatch {
475    /// Digest computed over the body (everything before the trailer).
476    pub expected: Vec<u8>,
477    /// Trailing bytes found in `bytes`.
478    pub found: Vec<u8>,
479}
480
481impl std::fmt::Display for TrailerMismatch {
482    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
483        write!(
484            f,
485            "trailer checksum mismatch (expected {}, found {})",
486            hex::encode(&self.expected),
487            hex::encode(&self.found)
488        )
489    }
490}
491
492impl std::error::Error for TrailerMismatch {}
493
494/// Verify that `bytes` ends with the hash of the preceding body.
495///
496/// # Errors
497///
498/// Returns [`TrailerMismatch`] when the trailer does not match, or when `bytes`
499/// is shorter than one digest for `algo`.
500pub fn verify_trailer(algo: HashAlgo, bytes: &[u8]) -> std::result::Result<(), TrailerMismatch> {
501    let trailer_len = algo.len();
502    if bytes.len() < trailer_len {
503        return Err(TrailerMismatch {
504            expected: Vec::new(),
505            found: bytes.to_vec(),
506        });
507    }
508    let split = bytes.len() - trailer_len;
509    let (body, trailer) = bytes.split_at(split);
510    let expected = algo.checksum_digest(body);
511    if expected.as_slice() == trailer {
512        Ok(())
513    } else {
514        Err(TrailerMismatch {
515            expected,
516            found: trailer.to_vec(),
517        })
518    }
519}
520
521/// Write `"<kind> <len>\\0"` into `buf` and return the number of bytes used.
522fn write_object_header(buf: &mut [u8], kind: ObjectKind, len: u64) -> usize {
523    let kind_bytes = kind.as_str().as_bytes();
524    let mut pos = 0;
525    buf[pos..pos + kind_bytes.len()].copy_from_slice(kind_bytes);
526    pos += kind_bytes.len();
527    buf[pos] = b' ';
528    pos += 1;
529    pos += write_decimal(&mut buf[pos..], len);
530    buf[pos] = 0;
531    pos + 1
532}
533
534fn write_decimal(out: &mut [u8], mut n: u64) -> usize {
535    if n == 0 {
536        out[0] = b'0';
537        return 1;
538    }
539    let mut tmp = [0u8; 20];
540    let mut digits = 0usize;
541    while n > 0 {
542        tmp[digits] = b'0' + (n % 10) as u8;
543        digits += 1;
544        n /= 10;
545    }
546    for i in 0..digits {
547        out[i] = tmp[digits - 1 - i];
548    }
549    digits
550}
551
552#[cfg(test)]
553mod tests {
554    use super::*;
555    use std::io::Cursor;
556
557    fn hex_oid(_algo: HashAlgo, hex: &str) -> ObjectId {
558        ObjectId::from_hex(hex).expect("test vector hex")
559    }
560
561    fn assert_digest(algo: HashAlgo, data: &[u8], expected_hex: &str) {
562        let got = algo.digest(data).expect("digest");
563        assert_eq!(got, hex_oid(algo, expected_hex), "digest mismatch");
564    }
565
566    fn assert_checksum_digest(algo: HashAlgo, data: &[u8], expected_hex: &str) {
567        let got = algo.checksum_digest(data);
568        assert_eq!(hex::encode(&got), expected_hex, "checksum digest mismatch");
569    }
570
571    #[test]
572    fn checksum_hasher_nist_vectors_sha1_sha256() {
573        assert_checksum_digest(
574            HashAlgo::Sha1,
575            b"",
576            "da39a3ee5e6b4b0d3255bfef95601890afd80709",
577        );
578        assert_checksum_digest(
579            HashAlgo::Sha1,
580            b"abc",
581            "a9993e364706816aba3e25717850c26c9cd0d89d",
582        );
583        assert_checksum_digest(
584            HashAlgo::Sha256,
585            b"",
586            "e3b0c44298fc1c149afbf4c8996fb92427ae41e4649b934ca495991b7852b855",
587        );
588        assert_checksum_digest(
589            HashAlgo::Sha256,
590            b"abc",
591            "ba7816bf8f01cfea414140de5dae2223b00361a396177a9cb410ff61f20015ad",
592        );
593    }
594
595    #[test]
596    fn checksum_hasher_matches_object_hasher_digest() {
597        let data: Vec<u8> = (0..512).map(|i| (i % 251) as u8).collect();
598        for algo in [HashAlgo::Sha1, HashAlgo::Sha256] {
599            let mut checksum = algo.checksum_hasher();
600            checksum.update(&data);
601            let checksum_bytes = checksum.finalize();
602            assert_eq!(
603                checksum_bytes,
604                algo.digest(&data).expect("digest").as_bytes()
605            );
606        }
607    }
608
609    #[test]
610    fn hashing_writer_uses_checksum_hasher() {
611        let body = b"streaming checksum body";
612        let mut buf = Vec::new();
613        {
614            let mut w = HashingWriter::new(HashAlgo::Sha256, Cursor::new(&mut buf));
615            w.write_all(body).unwrap();
616            let (_, digest) = w.finish().unwrap();
617            assert_eq!(
618                digest.as_bytes(),
619                HashAlgo::Sha256.checksum_digest(body).as_slice()
620            );
621        }
622        verify_trailer(HashAlgo::Sha256, &buf).expect("trailer valid");
623    }
624
625    #[test]
626    fn sha1_nist_vectors() {
627        assert_digest(
628            HashAlgo::Sha1,
629            b"",
630            "da39a3ee5e6b4b0d3255bfef95601890afd80709",
631        );
632        assert_digest(
633            HashAlgo::Sha1,
634            b"abc",
635            "a9993e364706816aba3e25717850c26c9cd0d89d",
636        );
637        assert_digest(
638            HashAlgo::Sha1,
639            b"abcdbcdecdefdefgefghfghighijhijkijkljklmklmnlmnomnopnopq",
640            "84983e441c3bd26ebaae4aa1f95129e5e54670f1",
641        );
642        let million_a = vec![b'a'; 1_000_000];
643        assert_digest(
644            HashAlgo::Sha1,
645            &million_a,
646            "34aa973cd4c4daa4f61eeb2bdbad27316534016f",
647        );
648    }
649
650    #[test]
651    fn sha256_nist_vectors() {
652        assert_digest(
653            HashAlgo::Sha256,
654            b"",
655            "e3b0c44298fc1c149afbf4c8996fb92427ae41e4649b934ca495991b7852b855",
656        );
657        assert_digest(
658            HashAlgo::Sha256,
659            b"abc",
660            "ba7816bf8f01cfea414140de5dae2223b00361a396177a9cb410ff61f20015ad",
661        );
662        assert_digest(
663            HashAlgo::Sha256,
664            b"abcdbcdecdefdefgefghfghighijhijkijkljklmklmnlmnomnopnopq",
665            "248d6a61d20638b8e5c026930c3e6039a33ce45964ff2167f6ecedd419db06c1",
666        );
667        let million_a = vec![b'a'; 1_000_000];
668        assert_digest(
669            HashAlgo::Sha256,
670            &million_a,
671            "cdc76e5c9914fb9281a1c7e284d73e67f1809a48a497200e046d39ccc7112cd0",
672        );
673    }
674
675    #[test]
676    fn incremental_matches_oneshot_random_splits() {
677        let data: Vec<u8> = (0..4096).map(|i| (i % 251) as u8).collect();
678        for algo in [HashAlgo::Sha1, HashAlgo::Sha256] {
679            let oneshot = algo.digest(&data).expect("digest");
680            let mut state = 0xdead_beef_u64;
681            let mut pos = 0usize;
682            let mut hasher = algo.hasher();
683            while pos < data.len() {
684                state = state
685                    .wrapping_mul(6364136223846793005)
686                    .wrapping_add(1442695040888963407);
687                let remaining = data.len() - pos;
688                let chunk = if remaining == 1 {
689                    1
690                } else {
691                    (state as usize % remaining).max(1)
692                };
693                hasher.update(&data[pos..pos + chunk]);
694                pos += chunk;
695            }
696            assert_eq!(hasher.finalize().expect("finalize"), oneshot);
697        }
698    }
699
700    #[test]
701    fn object_header_encoding() {
702        let kinds = [
703            (ObjectKind::Blob, "blob"),
704            (ObjectKind::Tree, "tree"),
705            (ObjectKind::Commit, "commit"),
706            (ObjectKind::Tag, "tag"),
707        ];
708        let lens = [0_u64, 1, 4_294_967_297];
709        let cases: Vec<(ObjectKind, u64, String)> = kinds
710            .iter()
711            .flat_map(|&(kind, name)| {
712                lens.iter()
713                    .map(move |&len| (kind, len, format!("{name} {len}\0")))
714            })
715            .collect();
716        for (kind, len, expect) in &cases {
717            let mut buf = [0u8; OBJECT_HEADER_BUF_LEN];
718            let n = write_object_header(&mut buf, *kind, *len);
719            assert_eq!(
720                &buf[..n],
721                expect.as_bytes(),
722                "header for {kind:?} len {len}"
723            );
724        }
725    }
726
727    #[test]
728    fn hash_object_all_kinds() {
729        for kind in [
730            ObjectKind::Blob,
731            ObjectKind::Tree,
732            ObjectKind::Commit,
733            ObjectKind::Tag,
734        ] {
735            for payload in [b"" as &[u8], b"x"] {
736                let mut hasher =
737                    ObjectHasher::for_object(HashAlgo::Sha1, kind, payload.len() as u64);
738                hasher.update(payload);
739                assert_eq!(
740                    hash_object(HashAlgo::Sha1, kind, payload).expect("hash"),
741                    hasher.finalize().expect("finalize")
742                );
743            }
744        }
745    }
746
747    /// Inner writer that accepts at most `max` bytes per `write` call.
748    struct PartialWrite {
749        max: usize,
750        buf: Vec<u8>,
751        fail: bool,
752    }
753
754    impl Write for PartialWrite {
755        fn write(&mut self, buf: &[u8]) -> io::Result<usize> {
756            if self.fail {
757                return Err(io::Error::new(
758                    io::ErrorKind::Other,
759                    "simulated write failure",
760                ));
761            }
762            let n = buf.len().min(self.max);
763            self.buf.extend_from_slice(&buf[..n]);
764            Ok(n)
765        }
766
767        fn flush(&mut self) -> io::Result<()> {
768            Ok(())
769        }
770    }
771
772    #[test]
773    fn hashing_writer_partial_write_checksum() {
774        let inner = PartialWrite {
775            max: 2,
776            buf: Vec::new(),
777            fail: false,
778        };
779        let mut w = HashingWriter::new(HashAlgo::Sha1, inner);
780        let n = w.write(b"abcdef").expect("write");
781        assert_eq!(n, 2);
782        assert_eq!(w.get_ref().buf, b"ab");
783        let (_, digest) = w.finish().expect("finish");
784        assert_eq!(
785            digest.as_bytes(),
786            HashAlgo::Sha1.checksum_digest(b"ab").as_slice()
787        );
788        assert_ne!(
789            digest.as_bytes(),
790            HashAlgo::Sha1.checksum_digest(b"abcdef").as_slice()
791        );
792    }
793
794    #[test]
795    fn hashing_writer_write_error_does_not_update_checksum() {
796        let inner = PartialWrite {
797            max: 64,
798            buf: Vec::new(),
799            fail: true,
800        };
801        let mut w = HashingWriter::new(HashAlgo::Sha1, inner);
802        assert!(w.write(b"abcdef").is_err());
803        w.get_mut().fail = false;
804        w.write_all(b"ab").expect("write");
805        let (_, digest) = w.finish().expect("finish");
806        assert_eq!(
807            digest.as_bytes(),
808            HashAlgo::Sha1.checksum_digest(b"ab").as_slice()
809        );
810    }
811
812    #[test]
813    fn hashing_writer_trailer_matches_digest() {
814        let body = b"index payload bytes";
815        let mut buf = Vec::new();
816        {
817            let mut w = HashingWriter::new(HashAlgo::Sha1, Cursor::new(&mut buf));
818            w.write_all(body).unwrap();
819            let (_, digest) = w.finish().unwrap();
820            assert_eq!(
821                digest.as_bytes(),
822                HashAlgo::Sha1.checksum_digest(body).as_slice()
823            );
824            assert_eq!(&buf[body.len()..], digest.as_bytes());
825        }
826        verify_trailer(HashAlgo::Sha1, &buf).expect("trailer valid");
827    }
828
829    #[test]
830    fn verify_trailer_mismatch_is_typed() {
831        let body = b"payload";
832        let mut file = body.to_vec();
833        file.extend_from_slice(&[0u8; 20]);
834        let err = verify_trailer(HashAlgo::Sha1, &file).unwrap_err();
835        assert!(matches!(err, TrailerMismatch { .. }));
836        assert_ne!(err.expected, err.found);
837    }
838
839    #[test]
840    fn finalize_into_and_write_trait() {
841        let mut hasher = HashAlgo::Sha256.hasher();
842        hasher.write_all(b"via write trait").unwrap();
843        let mut out = [0u8; 32];
844        let n = hasher.finalize_into(&mut out).unwrap();
845        assert_eq!(n, 32);
846        assert_eq!(
847            HashAlgo::Sha256.digest(b"via write trait").expect("digest"),
848            ObjectId::from_bytes(&out).unwrap()
849        );
850    }
851
852    #[test]
853    fn backend_matches_cpu() {
854        let expected = {
855            #[cfg(target_arch = "x86_64")]
856            {
857                if std::arch::is_x86_feature_detected!("sha") {
858                    Backend::X86ShaNi
859                } else {
860                    Backend::Portable
861                }
862            }
863            #[cfg(target_arch = "aarch64")]
864            {
865                if std::arch::is_aarch64_feature_detected!("sha2") {
866                    Backend::Aarch64Sha
867                } else {
868                    Backend::Portable
869                }
870            }
871            #[cfg(not(any(target_arch = "x86_64", target_arch = "aarch64")))]
872            {
873                Backend::Portable
874            }
875        };
876        assert_eq!(super::backend(HashAlgo::Sha1), expected);
877    }
878
879    #[test]
880    fn sha1_object_hasher_matches_sha1_crate_random() {
881        let mut state = 0x9e37_79b9_u64;
882        for len in [0_usize, 1, 63, 64, 65, 127, 128, 129, 512, 4096, 8192] {
883            let mut data = vec![0_u8; len];
884            for b in &mut data {
885                state = state.wrapping_mul(6364136223846793005).wrapping_add(1);
886                *b = (state >> 32) as u8;
887            }
888            let mut plain = Sha1::new();
889            plain.update(&data);
890            let expected = plain.finalize();
891            let mut hasher = ObjectHasher::new(HashAlgo::Sha1);
892            hasher.update(&data);
893            assert_eq!(
894                hasher.finalize().expect("finalize").as_bytes(),
895                expected.as_slice(),
896                "len {len}"
897            );
898        }
899    }
900
901    #[test]
902    fn finalize_detects_shattered_prefix() {
903        let dir = std::path::Path::new(env!("CARGO_MANIFEST_DIR")).join("tests/data");
904        for name in ["shattered-1-prefix.bin", "shattered-2-prefix.bin"] {
905            let bytes = std::fs::read(dir.join(name)).expect("fixture");
906            let mut hasher = ObjectHasher::new(HashAlgo::Sha1);
907            hasher.update(&bytes);
908            let err = hasher.finalize().expect_err("SHAttered block must collide");
909            assert!(matches!(
910                err,
911                Error::Object(ObjectError::HashCollision { .. })
912            ));
913            assert!(matches!(
914                HashAlgo::Sha1.digest(&bytes),
915                Err(Error::Object(ObjectError::HashCollision { .. }))
916            ));
917
918            // As a blob, the header shifts the colliding blocks: the object id is an
919            // ordinary SHA-1, exactly what Git computes for these files.
920            let mut plain = Sha1::new();
921            plain.update(format!("blob {}\0", bytes.len()).as_bytes());
922            plain.update(&bytes);
923            let oid = hash_object(HashAlgo::Sha1, ObjectKind::Blob, &bytes)
924                .expect("blob holding a SHAttered prefix is not a collision");
925            assert_eq!(oid.as_bytes(), plain.finalize().as_slice());
926        }
927    }
928
929    #[test]
930    fn sha256_finalize_never_collides() {
931        let data: Vec<u8> = (0..1024).map(|i| (i % 251) as u8).collect();
932        let mut hasher = ObjectHasher::new(HashAlgo::Sha256);
933        hasher.update(&data);
934        hasher
935            .finalize()
936            .expect("SHA-256 has no collision detection");
937    }
938
939    #[test]
940    fn sha256_backend_matches_sha2_dispatcher() {
941        #[cfg(target_arch = "x86_64")]
942        {
943            let got = super::backend(HashAlgo::Sha256);
944            if std::arch::is_x86_feature_detected!("sha") {
945                assert_eq!(got, Backend::X86ShaNi);
946            } else {
947                assert_eq!(got, Backend::Portable);
948            }
949        }
950    }
951}