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