1use super::{Digest, Felt, StarkField, DIGEST_SIZE, ZERO};
  2use crate::utils::{
  3    bytes_to_hex_string, hex_to_bytes, string::String, ByteReader, ByteWriter, Deserializable,
  4    DeserializationError, HexParseError, Serializable,
  5};
  6use core::{cmp::Ordering, fmt::Display, ops::Deref};
  7use winter_utils::Randomizable;
  8
  9/// The number of bytes needed to encoded a digest
 10pub const DIGEST_BYTES: usize = 32;
 11
 12// DIGEST TRAIT IMPLEMENTATIONS
 13// ================================================================================================
 14
 15#[derive(Debug, Default, Copy, Clone, Eq, PartialEq)]
 16#[cfg_attr(feature = "serde", derive(serde::Deserialize, serde::Serialize))]
 17#[cfg_attr(feature = "serde", serde(into = "String", try_from = "&str"))]
 18pub struct RpoDigest([Felt; DIGEST_SIZE]);
 19
 20impl RpoDigest {
 21    pub const fn new(value: [Felt; DIGEST_SIZE]) -> Self {
 22        Self(value)
 23    }
 24
 25    pub fn as_elements(&self) -> &[Felt] {
 26        self.as_ref()
 27    }
 28
 29    pub fn as_bytes(&self) -> [u8; DIGEST_BYTES] {
 30        <Self as Digest>::as_bytes(self)
 31    }
 32
 33    pub fn digests_as_elements<'a, I>(digests: I) -> impl Iterator<Item = &'a Felt>
 34    where
 35        I: Iterator<Item = &'a Self>,
 36    {
 37        digests.flat_map(|d| d.0.iter())
 38    }
 39}
 40
 41impl Digest for RpoDigest {
 42    fn as_bytes(&self) -> [u8; DIGEST_BYTES] {
 43        let mut result = [0; DIGEST_BYTES];
 44
 45        result[..8].copy_from_slice(&self.0[0].as_int().to_le_bytes());
 46        result[8..16].copy_from_slice(&self.0[1].as_int().to_le_bytes());
 47        result[16..24].copy_from_slice(&self.0[2].as_int().to_le_bytes());
 48        result[24..].copy_from_slice(&self.0[3].as_int().to_le_bytes());
 49
 50        result
 51    }
 52}
 53
 54impl Deref for RpoDigest {
 55    type Target = [Felt; DIGEST_SIZE];
 56
 57    fn deref(&self) -> &Self::Target {
 58        &self.0
 59    }
 60}
 61
 62impl Ord for RpoDigest {
 63    fn cmp(&self, other: &Self) -> Ordering {
 64        // compare the inner u64 of both elements.
 65        //
 66        // it will iterate the elements and will return the first computation different than
 67        // `Equal`. Otherwise, the ordering is equal.
 68        //
 69        // the endianness is irrelevant here because since, this being a cryptographically secure
 70        // hash computation, the digest shouldn't have any ordered property of its input.
 71        //
 72        // finally, we use `Felt::inner` instead of `Felt::as_int` so we avoid performing a
 73        // montgomery reduction for every limb. that is safe because every inner element of the
 74        // digest is guaranteed to be in its canonical form (that is, `x in [0,p)`).
 75        self.0.iter().map(Felt::inner).zip(other.0.iter().map(Felt::inner)).fold(
 76            Ordering::Equal,
 77            |ord, (a, b)| match ord {
 78                Ordering::Equal => a.cmp(&b),
 79                _ => ord,
 80            },
 81        )
 82    }
 83}
 84
 85impl PartialOrd for RpoDigest {
 86    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
 87        Some(self.cmp(other))
 88    }
 89}
 90
 91impl Display for RpoDigest {
 92    fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
 93        let encoded: String = self.into();
 94        write!(f, "{}", encoded)?;
 95        Ok(())
 96    }
 97}
 98
 99impl Randomizable for RpoDigest {
100    const VALUE_SIZE: usize = DIGEST_BYTES;
101
102    fn from_random_bytes(bytes: &[u8]) -> Option<Self> {
103        let bytes_array: Option<[u8; 32]> = bytes.try_into().ok();
104        if let Some(bytes_array) = bytes_array {
105            Self::try_from(bytes_array).ok()
106        } else {
107            None
108        }
109    }
110}
111
112// CONVERSIONS: FROM RPO DIGEST
113// ================================================================================================
114
115impl From<&RpoDigest> for [Felt; DIGEST_SIZE] {
116    fn from(value: &RpoDigest) -> Self {
117        value.0
118    }
119}
120
121impl From<RpoDigest> for [Felt; DIGEST_SIZE] {
122    fn from(value: RpoDigest) -> Self {
123        value.0
124    }
125}
126
127impl From<&RpoDigest> for [u64; DIGEST_SIZE] {
128    fn from(value: &RpoDigest) -> Self {
129        [
130            value.0[0].as_int(),
131            value.0[1].as_int(),
132            value.0[2].as_int(),
133            value.0[3].as_int(),
134        ]
135    }
136}
137
138impl From<RpoDigest> for [u64; DIGEST_SIZE] {
139    fn from(value: RpoDigest) -> Self {
140        [
141            value.0[0].as_int(),
142            value.0[1].as_int(),
143            value.0[2].as_int(),
144            value.0[3].as_int(),
145        ]
146    }
147}
148
149impl From<&RpoDigest> for [u8; DIGEST_BYTES] {
150    fn from(value: &RpoDigest) -> Self {
151        value.as_bytes()
152    }
153}
154
155impl From<RpoDigest> for [u8; DIGEST_BYTES] {
156    fn from(value: RpoDigest) -> Self {
157        value.as_bytes()
158    }
159}
160
161impl From<RpoDigest> for String {
162    /// The returned string starts with `0x`.
163    fn from(value: RpoDigest) -> Self {
164        bytes_to_hex_string(value.as_bytes())
165    }
166}
167
168impl From<&RpoDigest> for String {
169    /// The returned string starts with `0x`.
170    fn from(value: &RpoDigest) -> Self {
171        (*value).into()
172    }
173}
174
175// CONVERSIONS: TO DIGEST
176// ================================================================================================
177
178impl From<[Felt; DIGEST_SIZE]> for RpoDigest {
179    fn from(value: [Felt; DIGEST_SIZE]) -> Self {
180        Self(value)
181    }
182}
183
184impl TryFrom<[u8; DIGEST_BYTES]> for RpoDigest {
185    type Error = HexParseError;
186
187    fn try_from(value: [u8; DIGEST_BYTES]) -> Result<Self, Self::Error> {
188        // Note: the input length is known, the conversion from slice to array must succeed so the
189        // `unwrap`s below are safe
190        let a = u64::from_le_bytes(value[0..8].try_into().unwrap());
191        let b = u64::from_le_bytes(value[8..16].try_into().unwrap());
192        let c = u64::from_le_bytes(value[16..24].try_into().unwrap());
193        let d = u64::from_le_bytes(value[24..32].try_into().unwrap());
194
195        if [a, b, c, d].iter().any(|v| *v >= Felt::MODULUS) {
196            return Err(HexParseError::OutOfRange);
197        }
198
199        Ok(RpoDigest([Felt::new(a), Felt::new(b), Felt::new(c), Felt::new(d)]))
200    }
201}
202
203impl TryFrom<&str> for RpoDigest {
204    type Error = HexParseError;
205
206    /// Expects the string to start with `0x`.
207    fn try_from(value: &str) -> Result<Self, Self::Error> {
208        hex_to_bytes(value).and_then(|v| v.try_into())
209    }
210}
211
212impl TryFrom<String> for RpoDigest {
213    type Error = HexParseError;
214
215    /// Expects the string to start with `0x`.
216    fn try_from(value: String) -> Result<Self, Self::Error> {
217        value.as_str().try_into()
218    }
219}
220
221impl TryFrom<&String> for RpoDigest {
222    type Error = HexParseError;
223
224    /// Expects the string to start with `0x`.
225    fn try_from(value: &String) -> Result<Self, Self::Error> {
226        value.as_str().try_into()
227    }
228}
229
230// SERIALIZATION / DESERIALIZATION
231// ================================================================================================
232
233impl Serializable for RpoDigest {
234    fn write_into<W: ByteWriter>(&self, target: &mut W) {
235        target.write_bytes(&self.as_bytes());
236    }
237}
238
239impl Deserializable for RpoDigest {
240    fn read_from<R: ByteReader>(source: &mut R) -> Result<Self, DeserializationError> {
241        let mut inner: [Felt; DIGEST_SIZE] = [ZERO; DIGEST_SIZE];
242        for inner in inner.iter_mut() {
243            let e = source.read_u64()?;
244            if e >= Felt::MODULUS {
245                return Err(DeserializationError::InvalidValue(String::from(
246                    "Value not in the appropriate range",
247                )));
248            }
249            *inner = Felt::new(e);
250        }
251
252        Ok(Self(inner))
253    }
254}
255
256// TESTS
257// ================================================================================================
258
259#[cfg(test)]
260mod tests {
261    use super::{Deserializable, Felt, RpoDigest, Serializable, DIGEST_BYTES};
262    use crate::utils::SliceReader;
263    use rand_utils::rand_value;
264
265    #[test]
266    fn digest_serialization() {
267        let e1 = Felt::new(rand_value());
268        let e2 = Felt::new(rand_value());
269        let e3 = Felt::new(rand_value());
270        let e4 = Felt::new(rand_value());
271
272        let d1 = RpoDigest([e1, e2, e3, e4]);
273
274        let mut bytes = vec![];
275        d1.write_into(&mut bytes);
276        assert_eq!(DIGEST_BYTES, bytes.len());
277
278        let mut reader = SliceReader::new(&bytes);
279        let d2 = RpoDigest::read_from(&mut reader).unwrap();
280
281        assert_eq!(d1, d2);
282    }
283
284    #[test]
285    fn digest_encoding() {
286        let digest = RpoDigest([
287            Felt::new(rand_value()),
288            Felt::new(rand_value()),
289            Felt::new(rand_value()),
290            Felt::new(rand_value()),
291        ]);
292
293        let string: String = digest.into();
294        let round_trip: RpoDigest = string.try_into().expect("decoding failed");
295
296        assert_eq!(digest, round_trip);
297    }
298
299    #[test]
300    fn test_conversions() {
301        let digest = RpoDigest([
302            Felt::new(rand_value()),
303            Felt::new(rand_value()),
304            Felt::new(rand_value()),
305            Felt::new(rand_value()),
306        ]);
307
308        let v: [Felt; DIGEST_SIZE] = digest.into();
309        let v2: RpoDigest = v.into();
310        assert_eq!(digest, v2);
311
312        let v: [Felt; DIGEST_SIZE] = (&digest).into();
313        let v2: RpoDigest = v.into();
314        assert_eq!(digest, v2);
315
316        let v: [u64; DIGEST_SIZE] = digest.into();
317        let v2: RpoDigest = v.try_into().unwrap();
318        assert_eq!(digest, v2);
319
320        let v: [u64; DIGEST_SIZE] = (&digest).into();
321        let v2: RpoDigest = v.try_into().unwrap();
322        assert_eq!(digest, v2);
323
324        let v: [u8; DIGEST_BYTES] = digest.into();
325        let v2: RpoDigest = v.try_into().unwrap();
326        assert_eq!(digest, v2);
327
328        let v: [u8; DIGEST_BYTES] = (&digest).into();
329        let v2: RpoDigest = v.try_into().unwrap();
330        assert_eq!(digest, v2);
331
332        let v: String = digest.into();
333        let v2: RpoDigest = v.try_into().unwrap();
334        assert_eq!(digest, v2);
335
336        let v: String = (&digest).into();
337        let v2: RpoDigest = v.try_into().unwrap();
338        assert_eq!(digest, v2);
339
340        let v: [u8; DIGEST_BYTES] = digest.into();
341        let v2: RpoDigest = (&v).try_into().unwrap();
342        assert_eq!(digest, v2);
343
344        let v: [u8; DIGEST_BYTES] = (&digest).into();
345        let v2: RpoDigest = (&v).try_into().unwrap();
346        assert_eq!(digest, v2);
347    }
348}