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