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

miden_crypto/word/
mod.rs
