miden-crypto/src/hash/rescue/rpx/digest.rs
src/hash/rescue/rpx/digest.rsRaw
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 RpxDigest([Felt; DIGEST_SIZE]);
16
17impl RpxDigest {
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 RpxDigest {
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 RpxDigest {
57 type Target = [Felt; DIGEST_SIZE];
58
59 fn deref(&self) -> &Self::Target {
60 &self.0
61 }
62}
63
64impl Ord for RpxDigest {
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 RpxDigest {
88 fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
89 Some(self.cmp(other))
90 }
91}
92
93impl Display for RpxDigest {
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 RpxDigest {
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 RPX DIGEST
115// ================================================================================================
116
117impl From<&RpxDigest> for [Felt; DIGEST_SIZE] {
118 fn from(value: &RpxDigest) -> Self {
119 value.0
120 }
121}
122
123impl From<RpxDigest> for [Felt; DIGEST_SIZE] {
124 fn from(value: RpxDigest) -> Self {
125 value.0
126 }
127}
128
129impl From<&RpxDigest> for [u64; DIGEST_SIZE] {
130 fn from(value: &RpxDigest) -> 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<RpxDigest> for [u64; DIGEST_SIZE] {
141 fn from(value: RpxDigest) -> 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<&RpxDigest> for [u8; DIGEST_BYTES] {
152 fn from(value: &RpxDigest) -> Self {
153 value.as_bytes()
154 }
155}
156
157impl From<RpxDigest> for [u8; DIGEST_BYTES] {
158 fn from(value: RpxDigest) -> Self {
159 value.as_bytes()
160 }
161}
162
163impl From<RpxDigest> for String {
164 /// The returned string starts with `0x`.
165 fn from(value: RpxDigest) -> Self {
166 value.to_hex()
167 }
168}
169
170impl From<&RpxDigest> for String {
171 /// The returned string starts with `0x`.
172 fn from(value: &RpxDigest) -> Self {
173 (*value).into()
174 }
175}
176
177// CONVERSIONS: TO RPX DIGEST
178// ================================================================================================
179
180#[derive(Copy, Clone, Debug)]
181pub enum RpxDigestError {
182 /// The provided u64 integer does not fit in the field's moduli.
183 InvalidInteger,
184}
185
186impl From<&[Felt; DIGEST_SIZE]> for RpxDigest {
187 fn from(value: &[Felt; DIGEST_SIZE]) -> Self {
188 Self(*value)
189 }
190}
191
192impl From<[Felt; DIGEST_SIZE]> for RpxDigest {
193 fn from(value: [Felt; DIGEST_SIZE]) -> Self {
194 Self(value)
195 }
196}
197
198impl TryFrom<[u8; DIGEST_BYTES]> for RpxDigest {
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(RpxDigest([Felt::new(a), Felt::new(b), Felt::new(c), Felt::new(d)]))
214 }
215}
216
217impl TryFrom<&[u8; DIGEST_BYTES]> for RpxDigest {
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 RpxDigest {
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 RpxDigest {
234 type Error = RpxDigestError;
235
236 fn try_from(value: [u64; DIGEST_SIZE]) -> Result<Self, RpxDigestError> {
237 if value[0] >= Felt::MODULUS
238 || value[1] >= Felt::MODULUS
239 || value[2] >= Felt::MODULUS
240 || value[3] >= Felt::MODULUS
241 {
242 return Err(RpxDigestError::InvalidInteger);
243 }
244
245 Ok(Self([value[0].into(), value[1].into(), value[2].into(), value[3].into()]))
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 super::{Deserializable, Felt, RpxDigest, Serializable, DIGEST_BYTES, DIGEST_SIZE};
316 use crate::utils::{string::String, SliceReader};
317 use rand_utils::rand_value;
318
319 #[test]
320 fn digest_serialization() {
321 let e1 = Felt::new(rand_value());
322 let e2 = Felt::new(rand_value());
323 let e3 = Felt::new(rand_value());
324 let e4 = Felt::new(rand_value());
325
326 let d1 = RpxDigest([e1, e2, e3, e4]);
327
328 let mut bytes = vec![];
329 d1.write_into(&mut bytes);
330 assert_eq!(DIGEST_BYTES, bytes.len());
331
332 let mut reader = SliceReader::new(&bytes);
333 let d2 = RpxDigest::read_from(&mut reader).unwrap();
334
335 assert_eq!(d1, d2);
336 }
337
338 #[cfg(feature = "std")]
339 #[test]
340 fn digest_encoding() {
341 let digest = RpxDigest([
342 Felt::new(rand_value()),
343 Felt::new(rand_value()),
344 Felt::new(rand_value()),
345 Felt::new(rand_value()),
346 ]);
347
348 let string: String = digest.into();
349 let round_trip: RpxDigest = string.try_into().expect("decoding failed");
350
351 assert_eq!(digest, round_trip);
352 }
353
354 #[test]
355 fn test_conversions() {
356 let digest = RpxDigest([
357 Felt::new(rand_value()),
358 Felt::new(rand_value()),
359 Felt::new(rand_value()),
360 Felt::new(rand_value()),
361 ]);
362
363 let v: [Felt; DIGEST_SIZE] = digest.into();
364 let v2: RpxDigest = v.into();
365 assert_eq!(digest, v2);
366
367 let v: [Felt; DIGEST_SIZE] = (&digest).into();
368 let v2: RpxDigest = v.into();
369 assert_eq!(digest, v2);
370
371 let v: [u64; DIGEST_SIZE] = digest.into();
372 let v2: RpxDigest = v.try_into().unwrap();
373 assert_eq!(digest, v2);
374
375 let v: [u64; DIGEST_SIZE] = (&digest).into();
376 let v2: RpxDigest = v.try_into().unwrap();
377 assert_eq!(digest, v2);
378
379 let v: [u8; DIGEST_BYTES] = digest.into();
380 let v2: RpxDigest = v.try_into().unwrap();
381 assert_eq!(digest, v2);
382
383 let v: [u8; DIGEST_BYTES] = (&digest).into();
384 let v2: RpxDigest = v.try_into().unwrap();
385 assert_eq!(digest, v2);
386
387 let v: String = digest.into();
388 let v2: RpxDigest = v.try_into().unwrap();
389 assert_eq!(digest, v2);
390
391 let v: String = (&digest).into();
392 let v2: RpxDigest = v.try_into().unwrap();
393 assert_eq!(digest, v2);
394
395 let v: [u8; DIGEST_BYTES] = digest.into();
396 let v2: RpxDigest = (&v).try_into().unwrap();
397 assert_eq!(digest, v2);
398
399 let v: [u8; DIGEST_BYTES] = (&digest).into();
400 let v2: RpxDigest = (&v).try_into().unwrap();
401 assert_eq!(digest, v2);
402 }
403}