miden_crypto/word/
mod.rs

1//! A [Word] type used in the Miden protocol and associated utilities.
2
3use alloc::{string::String, vec::Vec};
4use core::{
5    cmp::Ordering,
6    fmt::Display,
7    hash::{Hash, Hasher},
8    ops::{Deref, DerefMut, Index, IndexMut, Range},
9    slice,
10};
11
12use thiserror::Error;
13use winter_crypto::Digest;
14
15const WORD_SIZE_FELT: usize = 4;
16const WORD_SIZE_BYTES: usize = 32;
17
18use super::{Felt, StarkField, ZERO};
19use crate::{
20    rand::Randomizable,
21    utils::{
22        ByteReader, ByteWriter, Deserializable, DeserializationError, HexParseError, Serializable,
23        bytes_to_hex_string, hex_to_bytes,
24    },
25};
26
27mod macros;
28pub use macros::parse_hex_string_as_word;
29
30mod lexicographic;
31pub use lexicographic::LexicographicWord;
32
33#[cfg(test)]
34mod tests;
35
36// WORD
37// ================================================================================================
38
39/// A unit of data consisting of 4 field elements.
40#[derive(Debug, Default, Copy, Clone, Eq, PartialEq)]
41#[cfg_attr(feature = "serde", derive(serde::Deserialize, serde::Serialize))]
42#[cfg_attr(feature = "serde", serde(into = "String", try_from = "&str"))]
43pub struct Word([Felt; WORD_SIZE_FELT]);
44
45impl Word {
46    /// The serialized size of the word in bytes.
47    pub const SERIALIZED_SIZE: usize = WORD_SIZE_BYTES;
48
49    /// Creates a new [Word] from the given field elements.
50    pub const fn new(value: [Felt; WORD_SIZE_FELT]) -> Self {
51        Self(value)
52    }
53
54    /// Returns the word as a slice of field elements.
55    pub fn as_elements(&self) -> &[Felt] {
56        self.as_ref()
57    }
58
59    /// Returns the word as a byte array.
60    pub fn as_bytes(&self) -> [u8; WORD_SIZE_BYTES] {
61        let mut result = [0; WORD_SIZE_BYTES];
62
63        result[..8].copy_from_slice(&self.0[0].as_int().to_le_bytes());
64        result[8..16].copy_from_slice(&self.0[1].as_int().to_le_bytes());
65        result[16..24].copy_from_slice(&self.0[2].as_int().to_le_bytes());
66        result[24..].copy_from_slice(&self.0[3].as_int().to_le_bytes());
67
68        result
69    }
70
71    /// Returns an iterator over the elements of multiple words.
72    pub(crate) fn words_as_elements_iter<'a, I>(words: I) -> impl Iterator<Item = &'a Felt>
73    where
74        I: Iterator<Item = &'a Self>,
75    {
76        words.flat_map(|d| d.0.iter())
77    }
78
79    /// Returns all elements of multiple words as a slice.
80    pub fn words_as_elements(words: &[Self]) -> &[Felt] {
81        let p = words.as_ptr();
82        let len = words.len() * WORD_SIZE_FELT;
83        unsafe { slice::from_raw_parts(p as *const Felt, len) }
84    }
85
86    /// Returns hexadecimal representation of this word prefixed with `0x`.
87    pub fn to_hex(&self) -> String {
88        bytes_to_hex_string(self.as_bytes())
89    }
90
91    /// Returns internal elements of this word as a vector.
92    pub fn to_vec(&self) -> Vec<Felt> {
93        self.0.to_vec()
94    }
95}
96
97impl Hash for Word {
98    fn hash<H: Hasher>(&self, state: &mut H) {
99        state.write(&self.as_bytes());
100    }
101}
102
103impl Digest for Word {
104    fn as_bytes(&self) -> [u8; WORD_SIZE_BYTES] {
105        self.as_bytes()
106    }
107}
108
109impl Deref for Word {
110    type Target = [Felt; WORD_SIZE_FELT];
111
112    fn deref(&self) -> &Self::Target {
113        &self.0
114    }
115}
116
117impl DerefMut for Word {
118    fn deref_mut(&mut self) -> &mut Self::Target {
119        &mut self.0
120    }
121}
122
123impl Index<usize> for Word {
124    type Output = Felt;
125
126    fn index(&self, index: usize) -> &Self::Output {
127        &self.0[index]
128    }
129}
130
131impl IndexMut<usize> for Word {
132    fn index_mut(&mut self, index: usize) -> &mut Self::Output {
133        &mut self.0[index]
134    }
135}
136
137impl Index<Range<usize>> for Word {
138    type Output = [Felt];
139
140    fn index(&self, index: Range<usize>) -> &Self::Output {
141        &self.0[index]
142    }
143}
144
145impl IndexMut<Range<usize>> for Word {
146    fn index_mut(&mut self, index: Range<usize>) -> &mut Self::Output {
147        &mut self.0[index]
148    }
149}
150
151impl Ord for Word {
152    fn cmp(&self, other: &Self) -> Ordering {
153        // Compare the inner u64 of both elements.
154        //
155        // It will iterate the elements and will return the first computation different than
156        // `Equal`. Otherwise, the ordering is equal.
157        //
158        // Finally, we use `Felt::inner` instead of `Felt::as_int` so we avoid performing a
159        // montgomery reduction for every limb. That is safe because every inner element of the
160        // word is guaranteed to be in its canonical form (that is, `x in [0,p)`).
161        //
162        // Because we don't perform Montgomery reduction, we must iterate over, and compare,
163        // each element. A simple bytestring comparison would be inappropriate because the `Word`s
164        // are represented in "lexicographical" order.
165        self.0.iter().map(Felt::inner).zip(other.0.iter().map(Felt::inner)).fold(
166            Ordering::Equal,
167            |ord, (a, b)| match ord {
168                Ordering::Equal => a.cmp(&b),
169                _ => ord,
170            },
171        )
172    }
173}
174
175impl PartialOrd for Word {
176    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
177        Some(self.cmp(other))
178    }
179}
180
181impl Display for Word {
182    fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
183        write!(f, "{}", self.to_hex())
184    }
185}
186
187impl Randomizable for Word {
188    const VALUE_SIZE: usize = WORD_SIZE_BYTES;
189
190    fn from_random_bytes(bytes: &[u8]) -> Option<Self> {
191        let bytes_array: Option<[u8; 32]> = bytes.try_into().ok();
192        if let Some(bytes_array) = bytes_array {
193            Self::try_from(bytes_array).ok()
194        } else {
195            None
196        }
197    }
198}
199
200// CONVERSIONS: FROM WORD
201// ================================================================================================
202
203/// Errors that can occur when working with a [Word].
204#[derive(Debug, Error)]
205pub enum WordError {
206    /// Hex-encoded field elements parsed are invalid.
207    #[error("hex encoded values of a word are invalid")]
208    HexParse(#[from] HexParseError),
209    /// Field element conversion failed due to invalid value.
210    #[error("failed to convert to field element: {0}")]
211    InvalidFieldElement(String),
212    /// Failed to convert a slice to an array of expected length.
213    #[error("invalid input length: expected {1} {0}, but received {2}")]
214    InvalidInputLength(&'static str, usize, usize),
215    /// Failed to convert the word's field elements to the specified type.
216    #[error("failed to convert the word's field elements to type {0}")]
217    TypeConversion(&'static str),
218}
219
220impl TryFrom<&Word> for [bool; WORD_SIZE_FELT] {
221    type Error = WordError;
222
223    fn try_from(value: &Word) -> Result<Self, Self::Error> {
224        (*value).try_into()
225    }
226}
227
228impl TryFrom<Word> for [bool; WORD_SIZE_FELT] {
229    type Error = WordError;
230
231    fn try_from(value: Word) -> Result<Self, Self::Error> {
232        fn to_bool(v: u64) -> Option<bool> {
233            if v <= 1 { Some(v == 1) } else { None }
234        }
235
236        Ok([
237            to_bool(value.0[0].as_int()).ok_or(WordError::TypeConversion("bool"))?,
238            to_bool(value.0[1].as_int()).ok_or(WordError::TypeConversion("bool"))?,
239            to_bool(value.0[2].as_int()).ok_or(WordError::TypeConversion("bool"))?,
240            to_bool(value.0[3].as_int()).ok_or(WordError::TypeConversion("bool"))?,
241        ])
242    }
243}
244
245impl TryFrom<&Word> for [u8; WORD_SIZE_FELT] {
246    type Error = WordError;
247
248    fn try_from(value: &Word) -> Result<Self, Self::Error> {
249        (*value).try_into()
250    }
251}
252
253impl TryFrom<Word> for [u8; WORD_SIZE_FELT] {
254    type Error = WordError;
255
256    fn try_from(value: Word) -> Result<Self, Self::Error> {
257        Ok([
258            value.0[0].as_int().try_into().map_err(|_| WordError::TypeConversion("u8"))?,
259            value.0[1].as_int().try_into().map_err(|_| WordError::TypeConversion("u8"))?,
260            value.0[2].as_int().try_into().map_err(|_| WordError::TypeConversion("u8"))?,
261            value.0[3].as_int().try_into().map_err(|_| WordError::TypeConversion("u8"))?,
262        ])
263    }
264}
265
266impl TryFrom<&Word> for [u16; WORD_SIZE_FELT] {
267    type Error = WordError;
268
269    fn try_from(value: &Word) -> Result<Self, Self::Error> {
270        (*value).try_into()
271    }
272}
273
274impl TryFrom<Word> for [u16; WORD_SIZE_FELT] {
275    type Error = WordError;
276
277    fn try_from(value: Word) -> Result<Self, Self::Error> {
278        Ok([
279            value.0[0].as_int().try_into().map_err(|_| WordError::TypeConversion("u16"))?,
280            value.0[1].as_int().try_into().map_err(|_| WordError::TypeConversion("u16"))?,
281            value.0[2].as_int().try_into().map_err(|_| WordError::TypeConversion("u16"))?,
282            value.0[3].as_int().try_into().map_err(|_| WordError::TypeConversion("u16"))?,
283        ])
284    }
285}
286
287impl TryFrom<&Word> for [u32; WORD_SIZE_FELT] {
288    type Error = WordError;
289
290    fn try_from(value: &Word) -> Result<Self, Self::Error> {
291        (*value).try_into()
292    }
293}
294
295impl TryFrom<Word> for [u32; WORD_SIZE_FELT] {
296    type Error = WordError;
297
298    fn try_from(value: Word) -> Result<Self, Self::Error> {
299        Ok([
300            value.0[0].as_int().try_into().map_err(|_| WordError::TypeConversion("u32"))?,
301            value.0[1].as_int().try_into().map_err(|_| WordError::TypeConversion("u32"))?,
302            value.0[2].as_int().try_into().map_err(|_| WordError::TypeConversion("u32"))?,
303            value.0[3].as_int().try_into().map_err(|_| WordError::TypeConversion("u32"))?,
304        ])
305    }
306}
307
308impl From<&Word> for [u64; WORD_SIZE_FELT] {
309    fn from(value: &Word) -> Self {
310        (*value).into()
311    }
312}
313
314impl From<Word> for [u64; WORD_SIZE_FELT] {
315    fn from(value: Word) -> Self {
316        [
317            value.0[0].as_int(),
318            value.0[1].as_int(),
319            value.0[2].as_int(),
320            value.0[3].as_int(),
321        ]
322    }
323}
324
325impl From<&Word> for [Felt; WORD_SIZE_FELT] {
326    fn from(value: &Word) -> Self {
327        (*value).into()
328    }
329}
330
331impl From<Word> for [Felt; WORD_SIZE_FELT] {
332    fn from(value: Word) -> Self {
333        value.0
334    }
335}
336
337impl From<&Word> for [u8; WORD_SIZE_BYTES] {
338    fn from(value: &Word) -> Self {
339        (*value).into()
340    }
341}
342
343impl From<Word> for [u8; WORD_SIZE_BYTES] {
344    fn from(value: Word) -> Self {
345        value.as_bytes()
346    }
347}
348
349impl From<&Word> for String {
350    /// The returned string starts with `0x`.
351    fn from(value: &Word) -> Self {
352        (*value).into()
353    }
354}
355
356impl From<Word> for String {
357    /// The returned string starts with `0x`.
358    fn from(value: Word) -> Self {
359        value.to_hex()
360    }
361}
362
363// CONVERSIONS: TO WORD
364// ================================================================================================
365
366impl From<&[bool; WORD_SIZE_FELT]> for Word {
367    fn from(value: &[bool; WORD_SIZE_FELT]) -> Self {
368        (*value).into()
369    }
370}
371
372impl From<[bool; WORD_SIZE_FELT]> for Word {
373    fn from(value: [bool; WORD_SIZE_FELT]) -> Self {
374        [value[0] as u32, value[1] as u32, value[2] as u32, value[3] as u32].into()
375    }
376}
377
378impl From<&[u8; WORD_SIZE_FELT]> for Word {
379    fn from(value: &[u8; WORD_SIZE_FELT]) -> Self {
380        (*value).into()
381    }
382}
383
384impl From<[u8; WORD_SIZE_FELT]> for Word {
385    fn from(value: [u8; WORD_SIZE_FELT]) -> Self {
386        Self([value[0].into(), value[1].into(), value[2].into(), value[3].into()])
387    }
388}
389
390impl From<&[u16; WORD_SIZE_FELT]> for Word {
391    fn from(value: &[u16; WORD_SIZE_FELT]) -> Self {
392        (*value).into()
393    }
394}
395
396impl From<[u16; WORD_SIZE_FELT]> for Word {
397    fn from(value: [u16; WORD_SIZE_FELT]) -> Self {
398        Self([value[0].into(), value[1].into(), value[2].into(), value[3].into()])
399    }
400}
401
402impl From<&[u32; WORD_SIZE_FELT]> for Word {
403    fn from(value: &[u32; WORD_SIZE_FELT]) -> Self {
404        (*value).into()
405    }
406}
407
408impl From<[u32; WORD_SIZE_FELT]> for Word {
409    fn from(value: [u32; WORD_SIZE_FELT]) -> Self {
410        Self([value[0].into(), value[1].into(), value[2].into(), value[3].into()])
411    }
412}
413
414impl TryFrom<&[u64; WORD_SIZE_FELT]> for Word {
415    type Error = WordError;
416
417    fn try_from(value: &[u64; WORD_SIZE_FELT]) -> Result<Self, WordError> {
418        (*value).try_into()
419    }
420}
421
422impl TryFrom<[u64; WORD_SIZE_FELT]> for Word {
423    type Error = WordError;
424
425    fn try_from(value: [u64; WORD_SIZE_FELT]) -> Result<Self, WordError> {
426        Ok(Self([
427            value[0].try_into().map_err(WordError::InvalidFieldElement)?,
428            value[1].try_into().map_err(WordError::InvalidFieldElement)?,
429            value[2].try_into().map_err(WordError::InvalidFieldElement)?,
430            value[3].try_into().map_err(WordError::InvalidFieldElement)?,
431        ]))
432    }
433}
434
435impl From<&[Felt; WORD_SIZE_FELT]> for Word {
436    fn from(value: &[Felt; WORD_SIZE_FELT]) -> Self {
437        Self(*value)
438    }
439}
440
441impl From<[Felt; WORD_SIZE_FELT]> for Word {
442    fn from(value: [Felt; WORD_SIZE_FELT]) -> Self {
443        Self(value)
444    }
445}
446
447impl TryFrom<&[u8; WORD_SIZE_BYTES]> for Word {
448    type Error = WordError;
449
450    fn try_from(value: &[u8; WORD_SIZE_BYTES]) -> Result<Self, Self::Error> {
451        (*value).try_into()
452    }
453}
454
455impl TryFrom<[u8; WORD_SIZE_BYTES]> for Word {
456    type Error = WordError;
457
458    fn try_from(value: [u8; WORD_SIZE_BYTES]) -> Result<Self, Self::Error> {
459        // Note: the input length is known, the conversion from slice to array must succeed so the
460        // `unwrap`s below are safe
461        let a = u64::from_le_bytes(value[0..8].try_into().unwrap());
462        let b = u64::from_le_bytes(value[8..16].try_into().unwrap());
463        let c = u64::from_le_bytes(value[16..24].try_into().unwrap());
464        let d = u64::from_le_bytes(value[24..32].try_into().unwrap());
465
466        let a: Felt = a.try_into().map_err(WordError::InvalidFieldElement)?;
467        let b: Felt = b.try_into().map_err(WordError::InvalidFieldElement)?;
468        let c: Felt = c.try_into().map_err(WordError::InvalidFieldElement)?;
469        let d: Felt = d.try_into().map_err(WordError::InvalidFieldElement)?;
470
471        Ok(Word([a, b, c, d]))
472    }
473}
474
475impl TryFrom<&[u8]> for Word {
476    type Error = WordError;
477
478    fn try_from(value: &[u8]) -> Result<Self, Self::Error> {
479        let value: [u8; WORD_SIZE_BYTES] = value
480            .try_into()
481            .map_err(|_| WordError::InvalidInputLength("bytes", WORD_SIZE_BYTES, value.len()))?;
482        value.try_into()
483    }
484}
485
486impl TryFrom<&[Felt]> for Word {
487    type Error = WordError;
488
489    fn try_from(value: &[Felt]) -> Result<Self, Self::Error> {
490        let value: [Felt; WORD_SIZE_FELT] = value
491            .try_into()
492            .map_err(|_| WordError::InvalidInputLength("elements", WORD_SIZE_FELT, value.len()))?;
493        Ok(value.into())
494    }
495}
496
497impl TryFrom<&str> for Word {
498    type Error = WordError;
499
500    /// Expects the string to start with `0x`.
501    fn try_from(value: &str) -> Result<Self, Self::Error> {
502        hex_to_bytes::<WORD_SIZE_BYTES>(value)
503            .map_err(WordError::HexParse)
504            .and_then(Word::try_from)
505    }
506}
507
508impl TryFrom<String> for Word {
509    type Error = WordError;
510
511    /// Expects the string to start with `0x`.
512    fn try_from(value: String) -> Result<Self, Self::Error> {
513        value.as_str().try_into()
514    }
515}
516
517impl TryFrom<&String> for Word {
518    type Error = WordError;
519
520    /// Expects the string to start with `0x`.
521    fn try_from(value: &String) -> Result<Self, Self::Error> {
522        value.as_str().try_into()
523    }
524}
525
526// SERIALIZATION / DESERIALIZATION
527// ================================================================================================
528
529impl Serializable for Word {
530    fn write_into<W: ByteWriter>(&self, target: &mut W) {
531        target.write_bytes(&self.as_bytes());
532    }
533
534    fn get_size_hint(&self) -> usize {
535        Self::SERIALIZED_SIZE
536    }
537}
538
539impl Deserializable for Word {
540    fn read_from<R: ByteReader>(source: &mut R) -> Result<Self, DeserializationError> {
541        let mut inner: [Felt; WORD_SIZE_FELT] = [ZERO; WORD_SIZE_FELT];
542        for inner in inner.iter_mut() {
543            let e = source.read_u64()?;
544            if e >= Felt::MODULUS {
545                return Err(DeserializationError::InvalidValue(String::from(
546                    "Value not in the appropriate range",
547                )));
548            }
549            *inner = Felt::new(e);
550        }
551
552        Ok(Self(inner))
553    }
554}
555
556// ITERATORS
557// ================================================================================================
558impl IntoIterator for Word {
559    type Item = Felt;
560    type IntoIter = <[Felt; 4] as IntoIterator>::IntoIter;
561
562    fn into_iter(self) -> Self::IntoIter {
563        self.0.into_iter()
564    }
565}
miden_crypto/word/mod.rs

miden_crypto/word/
mod.rs
