tig_core/
sha1.rs

1//! SHA-1 (RFC 3174)。
2//!
3//! git の object id と packfile の checksum 計算に用いる。ストリーミング入力に
4//! 対応し、固定サイズの内部状態 (window 64 byte) のみを持つ。
5//!
6//! SHA-1 は衝突攻撃が実証済みであり、暗号学的用途には使用しない。ここでは
7//! 既存 git repository との相互運用のための識別子としてのみ用いる。
8
9use crate::oid::Oid;
10
11pub struct Sha1 {
12    state: [u32; 5],
13    /// 入力の総 byte 数。
14    len: u64,
15    buf: [u8; 64],
16    buf_len: usize,
17}
18
19impl Default for Sha1 {
20    fn default() -> Self {
21        Self::new()
22    }
23}
24
25impl Sha1 {
26    pub const fn new() -> Self {
27        Self {
28            state: [
29                0x6745_2301,
30                0xefcd_ab89,
31                0x98ba_dcfe,
32                0x1032_5476,
33                0xc3d2_e1f0,
34            ],
35            len: 0,
36            buf: [0; 64],
37            buf_len: 0,
38        }
39    }
40
41    pub fn update(&mut self, mut data: &[u8]) {
42        self.len += data.len() as u64;
43
44        if self.buf_len > 0 {
45            let take = (64 - self.buf_len).min(data.len());
46            self.buf[self.buf_len..self.buf_len + take].copy_from_slice(&data[..take]);
47            self.buf_len += take;
48            data = &data[take..];
49            if self.buf_len < 64 {
50                // バッファが埋まらなかった (入力が尽きた)。以降の remainder 処理に
51                // 落とすと buf_len を上書きしてしまうため、ここで抜ける。
52                return;
53            }
54            let block = self.buf;
55            self.compress(&block);
56            self.buf_len = 0;
57        }
58
59        let mut chunks = data.chunks_exact(64);
60        for block in &mut chunks {
61            self.compress(block.try_into().unwrap());
62        }
63        let rest = chunks.remainder();
64        self.buf[..rest.len()].copy_from_slice(rest);
65        self.buf_len = rest.len();
66    }
67
68    pub fn finalize(mut self) -> [u8; 20] {
69        let bit_len = self.len * 8;
70        self.update(&[0x80]);
71        while self.buf_len != 56 {
72            self.update(&[0]);
73        }
74        // 上の update で len が進むが、bit_len は事前に確定済みのため影響しない。
75        self.update(&bit_len.to_be_bytes());
76        debug_assert_eq!(self.buf_len, 0);
77
78        let mut out = [0u8; 20];
79        for (i, word) in self.state.iter().enumerate() {
80            out[i * 4..i * 4 + 4].copy_from_slice(&word.to_be_bytes());
81        }
82        out
83    }
84
85    fn compress(&mut self, block: &[u8; 64]) {
86        let mut w = [0u32; 80];
87        for (i, chunk) in block.chunks_exact(4).enumerate() {
88            w[i] = u32::from_be_bytes(chunk.try_into().unwrap());
89        }
90        for i in 16..80 {
91            w[i] = (w[i - 3] ^ w[i - 8] ^ w[i - 14] ^ w[i - 16]).rotate_left(1);
92        }
93
94        let [mut a, mut b, mut c, mut d, mut e] = self.state;
95        for (i, &word) in w.iter().enumerate() {
96            let (f, k) = match i {
97                0..=19 => ((b & c) | (!b & d), 0x5a82_7999),
98                20..=39 => (b ^ c ^ d, 0x6ed9_eba1),
99                40..=59 => ((b & c) | (b & d) | (c & d), 0x8f1b_bcdc),
100                _ => (b ^ c ^ d, 0xca62_c1d6),
101            };
102            let t = a
103                .rotate_left(5)
104                .wrapping_add(f)
105                .wrapping_add(e)
106                .wrapping_add(k)
107                .wrapping_add(word);
108            e = d;
109            d = c;
110            c = b.rotate_left(30);
111            b = a;
112            a = t;
113        }
114
115        self.state[0] = self.state[0].wrapping_add(a);
116        self.state[1] = self.state[1].wrapping_add(b);
117        self.state[2] = self.state[2].wrapping_add(c);
118        self.state[3] = self.state[3].wrapping_add(d);
119        self.state[4] = self.state[4].wrapping_add(e);
120    }
121}
122
123/// 一括入力のダイジェスト計算。
124pub fn digest(data: &[u8]) -> [u8; 20] {
125    let mut h = Sha1::new();
126    h.update(data);
127    h.finalize()
128}
129
130/// ダイジェストを Oid として返す。
131pub fn digest_oid(parts: &[&[u8]]) -> Oid {
132    let mut h = Sha1::new();
133    for part in parts {
134        h.update(part);
135    }
136    Oid::from_bytes(h.finalize())
137}
138
139#[cfg(test)]
140mod tests {
141    use super::*;
142
143    fn hex(bytes: &[u8]) -> String {
144        bytes.iter().map(|b| format!("{b:02x}")).collect()
145    }
146
147    // RFC 3174 のテストベクタ。
148    #[test]
149    fn rfc3174_vectors() {
150        assert_eq!(
151            hex(&digest(b"abc")),
152            "a9993e364706816aba3e25717850c26c9cd0d89d"
153        );
154        assert_eq!(
155            hex(&digest(
156                b"abcdbcdecdefdefgefghfghighijhijkijkljklmklmnlmnomnopnopq"
157            )),
158            "84983e441c3bd26ebaae4aa1f95129e5e54670f1"
159        );
160        assert_eq!(
161            hex(&digest(&[b'a'; 1_000_000])),
162            "34aa973cd4c4daa4f61eeb2bdbad27316534016f"
163        );
164    }
165
166    #[test]
167    fn empty_input() {
168        assert_eq!(
169            hex(&digest(b"")),
170            "da39a3ee5e6b4b0d3255bfef95601890afd80709"
171        );
172    }
173
174    // 分割入力と一括入力が一致すること (境界 64 byte をまたぐケースを含む)。
175    #[test]
176    fn streaming_matches_oneshot() {
177        let data: Vec<u8> = (0..=255u8).cycle().take(1000).collect();
178        for split in [1usize, 63, 64, 65, 127, 500] {
179            let mut h = Sha1::new();
180            for chunk in data.chunks(split) {
181                h.update(chunk);
182            }
183            assert_eq!(h.finalize(), digest(&data), "split={split}");
184        }
185    }
186}
tig_core/sha1.rs

tig_core/
sha1.rs
