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