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, slice};
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 /// The serialized size of the digest in bytes.
23 pub const SERIALIZED_SIZE: usize = DIGEST_BYTES;
24
25 pub const fn new(value: [Felt; DIGEST_SIZE]) -> Self {
26 Self(value)
27 }
28
29 pub fn as_elements(&self) -> &[Felt] {
30 self.as_ref()
31 }
32
33 pub fn as_bytes(&self) -> [u8; DIGEST_BYTES] {
34 <Self as Digest>::as_bytes(self)
35 }
36
37 pub fn digests_as_elements_iter<'a, I>(digests: I) -> impl Iterator<Item = &'a Felt>
38 where
39 I: Iterator<Item = &'a Self>,
40 {
41 digests.flat_map(|d| d.0.iter())
42 }
43
44 pub fn digests_as_elements(digests: &[Self]) -> &[Felt] {
45 let p = digests.as_ptr();
46 let len = digests.len() * DIGEST_SIZE;
47 unsafe { slice::from_raw_parts(p as *const Felt, len) }
48 }
49
50 /// Returns hexadecimal representation of this digest prefixed with `0x`.
51 pub fn to_hex(&self) -> String {
52 bytes_to_hex_string(self.as_bytes())
53 }
54}
55
56impl Digest for RpxDigest {
57 fn as_bytes(&self) -> [u8; DIGEST_BYTES] {
58 let mut result = [0; DIGEST_BYTES];
59
60 result[..8].copy_from_slice(&self.0[0].as_int().to_le_bytes());
61 result[8..16].copy_from_slice(&self.0[1].as_int().to_le_bytes());
62 result[16..24].copy_from_slice(&self.0[2].as_int().to_le_bytes());
63 result[24..].copy_from_slice(&self.0[3].as_int().to_le_bytes());
64
65 result
66 }
67}
68
69impl Deref for RpxDigest {
70 type Target = [Felt; DIGEST_SIZE];
71
72 fn deref(&self) -> &Self::Target {
73 &self.0
74 }
75}
76
77impl Ord for RpxDigest {
78 fn cmp(&self, other: &Self) -> Ordering {
79 // compare the inner u64 of both elements.
80 //
81 // it will iterate the elements and will return the first computation different than
82 // `Equal`. Otherwise, the ordering is equal.
83 //
84 // the endianness is irrelevant here because since, this being a cryptographically secure
85 // hash computation, the digest shouldn't have any ordered property of its input.
86 //
87 // finally, we use `Felt::inner` instead of `Felt::as_int` so we avoid performing a
88 // montgomery reduction for every limb. that is safe because every inner element of the
89 // digest is guaranteed to be in its canonical form (that is, `x in [0,p)`).
90 self.0.iter().map(Felt::inner).zip(other.0.iter().map(Felt::inner)).fold(
91 Ordering::Equal,
92 |ord, (a, b)| match ord {
93 Ordering::Equal => a.cmp(&b),
94 _ => ord,
95 },
96 )
97 }
98}
99
100impl PartialOrd for RpxDigest {
101 fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
102 Some(self.cmp(other))
103 }
104}
105
106impl Display for RpxDigest {
107 fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
108 let encoded: String = self.into();
109 write!(f, "{}", encoded)?;
110 Ok(())
111 }
112}
113
114impl Randomizable for RpxDigest {
115 const VALUE_SIZE: usize = DIGEST_BYTES;
116
117 fn from_random_bytes(bytes: &[u8]) -> Option<Self> {
118 let bytes_array: Option<[u8; 32]> = bytes.try_into().ok();
119 if let Some(bytes_array) = bytes_array {
120 Self::try_from(bytes_array).ok()
121 } else {
122 None
123 }
124 }
125}
126
127// CONVERSIONS: FROM RPX DIGEST
128// ================================================================================================
129
130#[derive(Copy, Clone, Debug)]
131pub enum RpxDigestError {
132 InvalidInteger,
133}
134
135impl TryFrom<&RpxDigest> for [bool; DIGEST_SIZE] {
136 type Error = RpxDigestError;
137
138 fn try_from(value: &RpxDigest) -> Result<Self, Self::Error> {
139 (*value).try_into()
140 }
141}
142
143impl TryFrom<RpxDigest> for [bool; DIGEST_SIZE] {
144 type Error = RpxDigestError;
145
146 fn try_from(value: RpxDigest) -> Result<Self, Self::Error> {
147 fn to_bool(v: u64) -> Option<bool> {
148 if v <= 1 {
149 Some(v == 1)
150 } else {
151 None
152 }
153 }
154
155 Ok([
156 to_bool(value.0[0].as_int()).ok_or(RpxDigestError::InvalidInteger)?,
157 to_bool(value.0[1].as_int()).ok_or(RpxDigestError::InvalidInteger)?,
158 to_bool(value.0[2].as_int()).ok_or(RpxDigestError::InvalidInteger)?,
159 to_bool(value.0[3].as_int()).ok_or(RpxDigestError::InvalidInteger)?,
160 ])
161 }
162}
163
164impl TryFrom<&RpxDigest> for [u8; DIGEST_SIZE] {
165 type Error = RpxDigestError;
166
167 fn try_from(value: &RpxDigest) -> Result<Self, Self::Error> {
168 (*value).try_into()
169 }
170}
171
172impl TryFrom<RpxDigest> for [u8; DIGEST_SIZE] {
173 type Error = RpxDigestError;
174
175 fn try_from(value: RpxDigest) -> Result<Self, Self::Error> {
176 Ok([
177 value.0[0].as_int().try_into().map_err(|_| RpxDigestError::InvalidInteger)?,
178 value.0[1].as_int().try_into().map_err(|_| RpxDigestError::InvalidInteger)?,
179 value.0[2].as_int().try_into().map_err(|_| RpxDigestError::InvalidInteger)?,
180 value.0[3].as_int().try_into().map_err(|_| RpxDigestError::InvalidInteger)?,
181 ])
182 }
183}
184
185impl TryFrom<&RpxDigest> for [u16; DIGEST_SIZE] {
186 type Error = RpxDigestError;
187
188 fn try_from(value: &RpxDigest) -> Result<Self, Self::Error> {
189 (*value).try_into()
190 }
191}
192
193impl TryFrom<RpxDigest> for [u16; DIGEST_SIZE] {
194 type Error = RpxDigestError;
195
196 fn try_from(value: RpxDigest) -> Result<Self, Self::Error> {
197 Ok([
198 value.0[0].as_int().try_into().map_err(|_| RpxDigestError::InvalidInteger)?,
199 value.0[1].as_int().try_into().map_err(|_| RpxDigestError::InvalidInteger)?,
200 value.0[2].as_int().try_into().map_err(|_| RpxDigestError::InvalidInteger)?,
201 value.0[3].as_int().try_into().map_err(|_| RpxDigestError::InvalidInteger)?,
202 ])
203 }
204}
205
206impl TryFrom<&RpxDigest> for [u32; DIGEST_SIZE] {
207 type Error = RpxDigestError;
208
209 fn try_from(value: &RpxDigest) -> Result<Self, Self::Error> {
210 (*value).try_into()
211 }
212}
213
214impl TryFrom<RpxDigest> for [u32; DIGEST_SIZE] {
215 type Error = RpxDigestError;
216
217 fn try_from(value: RpxDigest) -> Result<Self, Self::Error> {
218 Ok([
219 value.0[0].as_int().try_into().map_err(|_| RpxDigestError::InvalidInteger)?,
220 value.0[1].as_int().try_into().map_err(|_| RpxDigestError::InvalidInteger)?,
221 value.0[2].as_int().try_into().map_err(|_| RpxDigestError::InvalidInteger)?,
222 value.0[3].as_int().try_into().map_err(|_| RpxDigestError::InvalidInteger)?,
223 ])
224 }
225}
226
227impl From<&RpxDigest> for [u64; DIGEST_SIZE] {
228 fn from(value: &RpxDigest) -> Self {
229 (*value).into()
230 }
231}
232
233impl From<RpxDigest> for [u64; DIGEST_SIZE] {
234 fn from(value: RpxDigest) -> Self {
235 [
236 value.0[0].as_int(),
237 value.0[1].as_int(),
238 value.0[2].as_int(),
239 value.0[3].as_int(),
240 ]
241 }
242}
243
244impl From<&RpxDigest> for [Felt; DIGEST_SIZE] {
245 fn from(value: &RpxDigest) -> Self {
246 value.0
247 }
248}
249
250impl From<RpxDigest> for [Felt; DIGEST_SIZE] {
251 fn from(value: RpxDigest) -> Self {
252 value.0
253 }
254}
255
256impl From<&RpxDigest> for [u8; DIGEST_BYTES] {
257 fn from(value: &RpxDigest) -> Self {
258 value.as_bytes()
259 }
260}
261
262impl From<RpxDigest> for [u8; DIGEST_BYTES] {
263 fn from(value: RpxDigest) -> Self {
264 value.as_bytes()
265 }
266}
267
268impl From<&RpxDigest> for String {
269 /// The returned string starts with `0x`.
270 fn from(value: &RpxDigest) -> Self {
271 (*value).into()
272 }
273}
274
275impl From<RpxDigest> for String {
276 /// The returned string starts with `0x`.
277 fn from(value: RpxDigest) -> Self {
278 value.to_hex()
279 }
280}
281
282// CONVERSIONS: TO RPX DIGEST
283// ================================================================================================
284
285impl From<&[bool; DIGEST_SIZE]> for RpxDigest {
286 fn from(value: &[bool; DIGEST_SIZE]) -> Self {
287 (*value).into()
288 }
289}
290
291impl From<[bool; DIGEST_SIZE]> for RpxDigest {
292 fn from(value: [bool; DIGEST_SIZE]) -> Self {
293 [value[0] as u32, value[1] as u32, value[2] as u32, value[3] as u32].into()
294 }
295}
296
297impl From<&[u8; DIGEST_SIZE]> for RpxDigest {
298 fn from(value: &[u8; DIGEST_SIZE]) -> Self {
299 (*value).into()
300 }
301}
302
303impl From<[u8; DIGEST_SIZE]> for RpxDigest {
304 fn from(value: [u8; DIGEST_SIZE]) -> Self {
305 Self([value[0].into(), value[1].into(), value[2].into(), value[3].into()])
306 }
307}
308
309impl From<&[u16; DIGEST_SIZE]> for RpxDigest {
310 fn from(value: &[u16; DIGEST_SIZE]) -> Self {
311 (*value).into()
312 }
313}
314
315impl From<[u16; DIGEST_SIZE]> for RpxDigest {
316 fn from(value: [u16; DIGEST_SIZE]) -> Self {
317 Self([value[0].into(), value[1].into(), value[2].into(), value[3].into()])
318 }
319}
320
321impl From<&[u32; DIGEST_SIZE]> for RpxDigest {
322 fn from(value: &[u32; DIGEST_SIZE]) -> Self {
323 (*value).into()
324 }
325}
326
327impl From<[u32; DIGEST_SIZE]> for RpxDigest {
328 fn from(value: [u32; DIGEST_SIZE]) -> Self {
329 Self([value[0].into(), value[1].into(), value[2].into(), value[3].into()])
330 }
331}
332
333impl TryFrom<&[u64; DIGEST_SIZE]> for RpxDigest {
334 type Error = RpxDigestError;
335
336 fn try_from(value: &[u64; DIGEST_SIZE]) -> Result<Self, RpxDigestError> {
337 (*value).try_into()
338 }
339}
340
341impl TryFrom<[u64; DIGEST_SIZE]> for RpxDigest {
342 type Error = RpxDigestError;
343
344 fn try_from(value: [u64; DIGEST_SIZE]) -> Result<Self, RpxDigestError> {
345 Ok(Self([
346 value[0].try_into().map_err(|_| RpxDigestError::InvalidInteger)?,
347 value[1].try_into().map_err(|_| RpxDigestError::InvalidInteger)?,
348 value[2].try_into().map_err(|_| RpxDigestError::InvalidInteger)?,
349 value[3].try_into().map_err(|_| RpxDigestError::InvalidInteger)?,
350 ]))
351 }
352}
353
354impl From<&[Felt; DIGEST_SIZE]> for RpxDigest {
355 fn from(value: &[Felt; DIGEST_SIZE]) -> Self {
356 Self(*value)
357 }
358}
359
360impl From<[Felt; DIGEST_SIZE]> for RpxDigest {
361 fn from(value: [Felt; DIGEST_SIZE]) -> Self {
362 Self(value)
363 }
364}
365
366impl TryFrom<&[u8; DIGEST_BYTES]> for RpxDigest {
367 type Error = HexParseError;
368
369 fn try_from(value: &[u8; DIGEST_BYTES]) -> Result<Self, Self::Error> {
370 (*value).try_into()
371 }
372}
373
374impl TryFrom<[u8; DIGEST_BYTES]> for RpxDigest {
375 type Error = HexParseError;
376
377 fn try_from(value: [u8; DIGEST_BYTES]) -> Result<Self, Self::Error> {
378 // Note: the input length is known, the conversion from slice to array must succeed so the
379 // `unwrap`s below are safe
380 let a = u64::from_le_bytes(value[0..8].try_into().unwrap());
381 let b = u64::from_le_bytes(value[8..16].try_into().unwrap());
382 let c = u64::from_le_bytes(value[16..24].try_into().unwrap());
383 let d = u64::from_le_bytes(value[24..32].try_into().unwrap());
384
385 if [a, b, c, d].iter().any(|v| *v >= Felt::MODULUS) {
386 return Err(HexParseError::OutOfRange);
387 }
388
389 Ok(RpxDigest([Felt::new(a), Felt::new(b), Felt::new(c), Felt::new(d)]))
390 }
391}
392
393impl TryFrom<&[u8]> for RpxDigest {
394 type Error = HexParseError;
395
396 fn try_from(value: &[u8]) -> Result<Self, Self::Error> {
397 (*value).try_into()
398 }
399}
400
401impl TryFrom<&str> for RpxDigest {
402 type Error = HexParseError;
403
404 /// Expects the string to start with `0x`.
405 fn try_from(value: &str) -> Result<Self, Self::Error> {
406 hex_to_bytes::<DIGEST_BYTES>(value).and_then(RpxDigest::try_from)
407 }
408}
409
410impl TryFrom<&String> for RpxDigest {
411 type Error = HexParseError;
412
413 /// Expects the string to start with `0x`.
414 fn try_from(value: &String) -> Result<Self, Self::Error> {
415 value.as_str().try_into()
416 }
417}
418
419impl TryFrom<String> for RpxDigest {
420 type Error = HexParseError;
421
422 /// Expects the string to start with `0x`.
423 fn try_from(value: String) -> Result<Self, Self::Error> {
424 value.as_str().try_into()
425 }
426}
427
428// SERIALIZATION / DESERIALIZATION
429// ================================================================================================
430
431impl Serializable for RpxDigest {
432 fn write_into<W: ByteWriter>(&self, target: &mut W) {
433 target.write_bytes(&self.as_bytes());
434 }
435
436 fn get_size_hint(&self) -> usize {
437 Self::SERIALIZED_SIZE
438 }
439}
440
441impl Deserializable for RpxDigest {
442 fn read_from<R: ByteReader>(source: &mut R) -> Result<Self, DeserializationError> {
443 let mut inner: [Felt; DIGEST_SIZE] = [ZERO; DIGEST_SIZE];
444 for inner in inner.iter_mut() {
445 let e = source.read_u64()?;
446 if e >= Felt::MODULUS {
447 return Err(DeserializationError::InvalidValue(String::from(
448 "Value not in the appropriate range",
449 )));
450 }
451 *inner = Felt::new(e);
452 }
453
454 Ok(Self(inner))
455 }
456}
457
458// ITERATORS
459// ================================================================================================
460impl IntoIterator for RpxDigest {
461 type Item = Felt;
462 type IntoIter = <[Felt; 4] as IntoIterator>::IntoIter;
463
464 fn into_iter(self) -> Self::IntoIter {
465 self.0.into_iter()
466 }
467}
468
469// TESTS
470// ================================================================================================
471
472#[cfg(test)]
473mod tests {
474 use alloc::string::String;
475
476 use rand_utils::rand_value;
477
478 use super::{Deserializable, Felt, RpxDigest, Serializable, DIGEST_BYTES, DIGEST_SIZE};
479 use crate::utils::SliceReader;
480
481 #[test]
482 fn digest_serialization() {
483 let e1 = Felt::new(rand_value());
484 let e2 = Felt::new(rand_value());
485 let e3 = Felt::new(rand_value());
486 let e4 = Felt::new(rand_value());
487
488 let d1 = RpxDigest([e1, e2, e3, e4]);
489
490 let mut bytes = vec![];
491 d1.write_into(&mut bytes);
492 assert_eq!(DIGEST_BYTES, bytes.len());
493 assert_eq!(bytes.len(), d1.get_size_hint());
494
495 let mut reader = SliceReader::new(&bytes);
496 let d2 = RpxDigest::read_from(&mut reader).unwrap();
497
498 assert_eq!(d1, d2);
499 }
500
501 #[test]
502 fn digest_encoding() {
503 let digest = RpxDigest([
504 Felt::new(rand_value()),
505 Felt::new(rand_value()),
506 Felt::new(rand_value()),
507 Felt::new(rand_value()),
508 ]);
509
510 let string: String = digest.into();
511 let round_trip: RpxDigest = string.try_into().expect("decoding failed");
512
513 assert_eq!(digest, round_trip);
514 }
515
516 #[test]
517 fn test_conversions() {
518 let digest = RpxDigest([
519 Felt::new(rand_value()),
520 Felt::new(rand_value()),
521 Felt::new(rand_value()),
522 Felt::new(rand_value()),
523 ]);
524
525 // BY VALUE
526 // ----------------------------------------------------------------------------------------
527 let v: [bool; DIGEST_SIZE] = [true, false, true, true];
528 let v2: RpxDigest = v.into();
529 assert_eq!(v, <[bool; DIGEST_SIZE]>::try_from(v2).unwrap());
530
531 let v: [u8; DIGEST_SIZE] = [0_u8, 1_u8, 2_u8, 3_u8];
532 let v2: RpxDigest = v.into();
533 assert_eq!(v, <[u8; DIGEST_SIZE]>::try_from(v2).unwrap());
534
535 let v: [u16; DIGEST_SIZE] = [0_u16, 1_u16, 2_u16, 3_u16];
536 let v2: RpxDigest = v.into();
537 assert_eq!(v, <[u16; DIGEST_SIZE]>::try_from(v2).unwrap());
538
539 let v: [u32; DIGEST_SIZE] = [0_u32, 1_u32, 2_u32, 3_u32];
540 let v2: RpxDigest = v.into();
541 assert_eq!(v, <[u32; DIGEST_SIZE]>::try_from(v2).unwrap());
542
543 let v: [u64; DIGEST_SIZE] = digest.into();
544 let v2: RpxDigest = v.try_into().unwrap();
545 assert_eq!(digest, v2);
546
547 let v: [Felt; DIGEST_SIZE] = digest.into();
548 let v2: RpxDigest = v.into();
549 assert_eq!(digest, v2);
550
551 let v: [u8; DIGEST_BYTES] = digest.into();
552 let v2: RpxDigest = v.try_into().unwrap();
553 assert_eq!(digest, v2);
554
555 let v: String = digest.into();
556 let v2: RpxDigest = v.try_into().unwrap();
557 assert_eq!(digest, v2);
558
559 // BY REF
560 // ----------------------------------------------------------------------------------------
561 let v: [bool; DIGEST_SIZE] = [true, false, true, true];
562 let v2: RpxDigest = (&v).into();
563 assert_eq!(v, <[bool; DIGEST_SIZE]>::try_from(&v2).unwrap());
564
565 let v: [u8; DIGEST_SIZE] = [0_u8, 1_u8, 2_u8, 3_u8];
566 let v2: RpxDigest = (&v).into();
567 assert_eq!(v, <[u8; DIGEST_SIZE]>::try_from(&v2).unwrap());
568
569 let v: [u16; DIGEST_SIZE] = [0_u16, 1_u16, 2_u16, 3_u16];
570 let v2: RpxDigest = (&v).into();
571 assert_eq!(v, <[u16; DIGEST_SIZE]>::try_from(&v2).unwrap());
572
573 let v: [u32; DIGEST_SIZE] = [0_u32, 1_u32, 2_u32, 3_u32];
574 let v2: RpxDigest = (&v).into();
575 assert_eq!(v, <[u32; DIGEST_SIZE]>::try_from(&v2).unwrap());
576
577 let v: [u64; DIGEST_SIZE] = (&digest).into();
578 let v2: RpxDigest = (&v).try_into().unwrap();
579 assert_eq!(digest, v2);
580
581 let v: [Felt; DIGEST_SIZE] = (&digest).into();
582 let v2: RpxDigest = (&v).into();
583 assert_eq!(digest, v2);
584
585 let v: [u8; DIGEST_BYTES] = (&digest).into();
586 let v2: RpxDigest = (&v).try_into().unwrap();
587 assert_eq!(digest, v2);
588
589 let v: String = (&digest).into();
590 let v2: RpxDigest = (&v).try_into().unwrap();
591 assert_eq!(digest, v2);
592 }
593}