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