mopenzl 0.2.1

//! SHA-256 (FIPS 180-4), the digest OpenZL derives dictionary and bundle IDs
//! from (`ZL_UniqueID_computeSHA256`, common/sha256.c).
//!
//! A plain scalar implementation: dictionaries are hashed once, when they
//! are built or loaded, so the digest is nowhere near a hot path. The tests
//! check the NIST vectors and, against the C library, random inputs of every
//! padding shape.

use alloc::vec::Vec;

/// Bytes of a digest.
pub(crate) const DIGEST_LEN: usize = 32;

/// Bytes of one message block.
const BLOCK_LEN: usize = 64;

/// The initial hash value (FIPS 180-4 section 5.3.3).
const INITIAL: [u32; 8] = [
    0x6a09_e667,
    0xbb67_ae85,
    0x3c6e_f372,
    0xa54f_f53a,
    0x510e_527f,
    0x9b05_688c,
    0x1f83_d9ab,
    0x5be0_cd19,
];

/// The round constants (FIPS 180-4 section 4.2.2).
const K: [u32; 64] = [
    0x428a_2f98,
    0x7137_4491,
    0xb5c0_fbcf,
    0xe9b5_dba5,
    0x3956_c25b,
    0x59f1_11f1,
    0x923f_82a4,
    0xab1c_5ed5,
    0xd807_aa98,
    0x1283_5b01,
    0x2431_85be,
    0x550c_7dc3,
    0x72be_5d74,
    0x80de_b1fe,
    0x9bdc_06a7,
    0xc19b_f174,
    0xe49b_69c1,
    0xefbe_4786,
    0x0fc1_9dc6,
    0x240c_a1cc,
    0x2de9_2c6f,
    0x4a74_84aa,
    0x5cb0_a9dc,
    0x76f9_88da,
    0x983e_5152,
    0xa831_c66d,
    0xb003_27c8,
    0xbf59_7fc7,
    0xc6e0_0bf3,
    0xd5a7_9147,
    0x06ca_6351,
    0x1429_2967,
    0x27b7_0a85,
    0x2e1b_2138,
    0x4d2c_6dfc,
    0x5338_0d13,
    0x650a_7354,
    0x766a_0abb,
    0x81c2_c92e,
    0x9272_2c85,
    0xa2bf_e8a1,
    0xa81a_664b,
    0xc24b_8b70,
    0xc76c_51a3,
    0xd192_e819,
    0xd699_0624,
    0xf40e_3585,
    0x106a_a070,
    0x19a4_c116,
    0x1e37_6c08,
    0x2748_774c,
    0x34b0_bcb5,
    0x391c_0cb3,
    0x4ed8_aa4a,
    0x5b9c_ca4f,
    0x682e_6ff3,
    0x748f_82ee,
    0x78a5_636f,
    0x84c8_7814,
    0x8cc7_0208,
    0x90be_fffa,
    0xa450_6ceb,
    0xbef9_a3f7,
    0xc671_78f2,
];

/// Compresses one 64-byte `block` into `state` (FIPS 180-4 section 6.2.2).
fn compress(state: &mut [u32; 8], block: &[u8; BLOCK_LEN]) {
    let mut schedule = [0u32; 64];
    for (word, bytes) in schedule.iter_mut().zip(block.as_chunks::<4>().0) {
        *word = u32::from_be_bytes(*bytes);
    }
    for t in 16..64 {
        let s0 = schedule[t - 15].rotate_right(7)
            ^ schedule[t - 15].rotate_right(18)
            ^ (schedule[t - 15] >> 3);
        let s1 = schedule[t - 2].rotate_right(17)
            ^ schedule[t - 2].rotate_right(19)
            ^ (schedule[t - 2] >> 10);
        schedule[t] = schedule[t - 16]
            .wrapping_add(s0)
            .wrapping_add(schedule[t - 7])
            .wrapping_add(s1);
    }
    let [mut a, mut b, mut c, mut d, mut e, mut f, mut g, mut h] = *state;
    for t in 0..64 {
        let big_s1 = e.rotate_right(6) ^ e.rotate_right(11) ^ e.rotate_right(25);
        let choose = (e & f) ^ (!e & g);
        let first = h
            .wrapping_add(big_s1)
            .wrapping_add(choose)
            .wrapping_add(K[t])
            .wrapping_add(schedule[t]);
        let big_s0 = a.rotate_right(2) ^ a.rotate_right(13) ^ a.rotate_right(22);
        let majority = (a & b) ^ (a & c) ^ (b & c);
        let second = big_s0.wrapping_add(majority);
        h = g;
        g = f;
        f = e;
        e = d.wrapping_add(first);
        d = c;
        c = b;
        b = a;
        a = first.wrapping_add(second);
    }
    for (word, add) in state.iter_mut().zip([a, b, c, d, e, f, g, h]) {
        *word = word.wrapping_add(add);
    }
}

/// The SHA-256 digest of `data`.
pub(crate) fn digest(data: &[u8]) -> [u8; DIGEST_LEN] {
    let mut state = INITIAL;
    let (blocks, tail) = data.as_chunks::<BLOCK_LEN>();
    for block in blocks {
        compress(&mut state, block);
    }
    // The tail, a 0x80 byte, zeros and the bit length fill one or two blocks.
    let mut padded: Vec<u8> = Vec::with_capacity(2 * BLOCK_LEN);
    padded.extend_from_slice(tail);
    padded.push(0x80);
    while padded.len() % BLOCK_LEN != BLOCK_LEN - 8 {
        padded.push(0);
    }
    padded.extend_from_slice(&((data.len() as u64).wrapping_mul(8)).to_be_bytes());
    for block in padded.as_chunks::<BLOCK_LEN>().0 {
        compress(&mut state, block);
    }
    let mut out = [0u8; DIGEST_LEN];
    for (bytes, word) in out.as_chunks_mut::<4>().0.iter_mut().zip(state) {
        *bytes = word.to_be_bytes();
    }
    out
}

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

    fn hex(bytes: &[u8]) -> alloc::string::String {
        use core::fmt::Write;
        bytes.iter().fold(alloc::string::String::new(), |mut s, b| {
            let _ = write!(s, "{b:02x}");
            s
        })
    }

    #[test]
    fn nist_vectors_hash_as_published() {
        assert_eq!(
            hex(&digest(b"")),
            "e3b0c44298fc1c149afbf4c8996fb92427ae41e4649b934ca495991b7852b855"
        );
        assert_eq!(
            hex(&digest(b"abc")),
            "ba7816bf8f01cfea414140de5dae2223b00361a396177a9cb410ff61f20015ad"
        );
        assert_eq!(
            hex(&digest(
                b"abcdbcdecdefdefgefghfghighijhijkijkljklmklmnlmnomnopnopq"
            )),
            "248d6a61d20638b8e5c026930c3e6039a33ce45964ff2167f6ecedd419db06c1"
        );
    }

    #[test]
    fn a_million_a_bytes_hash_as_published() {
        let data = alloc::vec![b'a'; 1_000_000];
        assert_eq!(
            hex(&digest(&data)),
            "cdc76e5c9914fb9281a1c7e284d73e67f1809a48a497200e046d39ccc7112cd0"
        );
    }

    #[test]
    fn every_padding_shape_matches_the_reference_library() {
        // Lengths around the one-block and two-block padding boundaries.
        for len in (0..200).chain([1000, 4095, 4096, 4097]) {
            let data: alloc::vec::Vec<u8> = (0..len as u32)
                .map(|i| i.wrapping_mul(2_654_435_761).to_le_bytes()[2])
                .collect();
            assert_eq!(
                digest(&data),
                openzl_ffi::enc_dict::sha256(&data),
                "{len} bytes"
            );
        }
    }
}