midenc_debug/
felt.rs

1use std::collections::VecDeque;
2
3use miden_core::StarkField;
4use miden_processor::Felt as RawFelt;
5use proptest::{
6    arbitrary::Arbitrary,
7    strategy::{BoxedStrategy, Strategy},
8};
9use serde::Deserialize;
10
11pub trait PushToStack: Sized {
12    fn try_push(&self, stack: &mut Vec<RawFelt>) {
13        let mut ptr = self as *const Self as *const u8;
14        let mut num_bytes = core::mem::size_of::<Self>();
15        let mut buf = Vec::with_capacity(num_bytes / core::mem::size_of::<u32>());
16        while num_bytes > 0 {
17            let mut next = [0u8; 4];
18            let consume = core::cmp::min(4, num_bytes);
19            unsafe {
20                ptr.copy_to_nonoverlapping(next.as_mut_ptr(), consume);
21                ptr = ptr.byte_add(consume);
22            }
23            num_bytes -= consume;
24            buf.push(RawFelt::new(u32::from_be_bytes(next) as u64));
25        }
26
27        for item in buf.into_iter().rev() {
28            stack.push(item);
29        }
30    }
31}
32
33pub trait PopFromStack: Sized {
34    fn try_pop(stack: &mut VecDeque<Felt>) -> Option<Self> {
35        use core::mem::MaybeUninit;
36
37        let mut num_bytes = core::mem::size_of::<Self>();
38        let mut result = MaybeUninit::<Self>::uninit();
39        let mut ptr = result.as_mut_ptr() as *mut u8;
40        while num_bytes > 0 {
41            let next = stack.pop_front().expect("expected more operand stack elements");
42            let next_bytes = (next.0.as_int() as u32).to_be_bytes();
43            let consume = core::cmp::min(4, num_bytes);
44            unsafe {
45                next_bytes.as_ptr().copy_to_nonoverlapping(ptr, consume);
46                ptr = ptr.byte_add(consume);
47            }
48            num_bytes -= consume;
49        }
50        Some(unsafe { result.assume_init() })
51    }
52}
53
54impl PushToStack for bool {
55    fn try_push(&self, stack: &mut Vec<RawFelt>) {
56        stack.push(RawFelt::new(*self as u64))
57    }
58}
59impl PopFromStack for bool {
60    fn try_pop(stack: &mut VecDeque<Felt>) -> Option<Self> {
61        Some(stack.pop_front().unwrap().0.as_int() != 0)
62    }
63}
64
65impl PushToStack for u8 {
66    fn try_push(&self, stack: &mut Vec<RawFelt>) {
67        stack.push(RawFelt::new(*self as u64))
68    }
69}
70impl PopFromStack for u8 {
71    fn try_pop(stack: &mut VecDeque<Felt>) -> Option<Self> {
72        Some(stack.pop_front().unwrap().0.as_int() as u8)
73    }
74}
75
76impl PushToStack for i8 {
77    fn try_push(&self, stack: &mut Vec<RawFelt>) {
78        stack.push(RawFelt::new(*self as u8 as u64))
79    }
80}
81impl PopFromStack for i8 {
82    fn try_pop(stack: &mut VecDeque<Felt>) -> Option<Self> {
83        Some(stack.pop_front().unwrap().0.as_int() as i8)
84    }
85}
86
87impl PushToStack for u16 {
88    fn try_push(&self, stack: &mut Vec<RawFelt>) {
89        stack.push(RawFelt::new(*self as u64))
90    }
91}
92impl PopFromStack for u16 {
93    fn try_pop(stack: &mut VecDeque<Felt>) -> Option<Self> {
94        Some(stack.pop_front().unwrap().0.as_int() as u16)
95    }
96}
97
98impl PushToStack for i16 {
99    fn try_push(&self, stack: &mut Vec<RawFelt>) {
100        stack.push(RawFelt::new(*self as u16 as u64))
101    }
102}
103impl PopFromStack for i16 {
104    fn try_pop(stack: &mut VecDeque<Felt>) -> Option<Self> {
105        Some(stack.pop_front().unwrap().0.as_int() as i16)
106    }
107}
108
109impl PushToStack for u32 {
110    fn try_push(&self, stack: &mut Vec<RawFelt>) {
111        stack.push(RawFelt::new(*self as u64))
112    }
113}
114impl PopFromStack for u32 {
115    fn try_pop(stack: &mut VecDeque<Felt>) -> Option<Self> {
116        Some(stack.pop_front().unwrap().0.as_int() as u32)
117    }
118}
119
120impl PushToStack for i32 {
121    fn try_push(&self, stack: &mut Vec<RawFelt>) {
122        stack.push(RawFelt::new(*self as u32 as u64))
123    }
124}
125impl PopFromStack for i32 {
126    fn try_pop(stack: &mut VecDeque<Felt>) -> Option<Self> {
127        Some(stack.pop_front().unwrap().0.as_int() as i32)
128    }
129}
130
131impl PushToStack for u64 {
132    fn try_push(&self, stack: &mut Vec<RawFelt>) {
133        let lo = self.rem_euclid(2u64.pow(32));
134        let hi = self.div_euclid(2u64.pow(32));
135        stack.push(RawFelt::new(lo));
136        stack.push(RawFelt::new(hi));
137    }
138}
139impl PopFromStack for u64 {
140    fn try_pop(stack: &mut VecDeque<Felt>) -> Option<Self> {
141        let hi = stack.pop_front().unwrap().0.as_int() * 2u64.pow(32);
142        let lo = stack.pop_front().unwrap().0.as_int();
143        Some(hi + lo)
144    }
145}
146
147impl PushToStack for i64 {
148    fn try_push(&self, stack: &mut Vec<RawFelt>) {
149        (*self as u64).try_push(stack)
150    }
151}
152impl PopFromStack for i64 {
153    fn try_pop(stack: &mut VecDeque<Felt>) -> Option<Self> {
154        u64::try_pop(stack).map(|value| value as i64)
155    }
156}
157
158impl PushToStack for u128 {
159    fn try_push(&self, stack: &mut Vec<RawFelt>) {
160        let lo = self.rem_euclid(2u128.pow(64));
161        let hi = self.div_euclid(2u128.pow(64));
162        (lo as u64).try_push(stack);
163        (hi as u64).try_push(stack);
164    }
165}
166impl PopFromStack for u128 {
167    fn try_pop(stack: &mut VecDeque<Felt>) -> Option<Self> {
168        let hi = (u64::try_pop(stack).unwrap() as u128) * 2u128.pow(64);
169        let lo = u64::try_pop(stack).unwrap() as u128;
170        Some(hi + lo)
171    }
172}
173
174impl PushToStack for i128 {
175    fn try_push(&self, stack: &mut Vec<RawFelt>) {
176        (*self as u128).try_push(stack)
177    }
178}
179impl PopFromStack for i128 {
180    fn try_pop(stack: &mut VecDeque<Felt>) -> Option<Self> {
181        u128::try_pop(stack).map(|value| value as i128)
182    }
183}
184
185impl PushToStack for RawFelt {
186    #[inline(always)]
187    fn try_push(&self, stack: &mut Vec<RawFelt>) {
188        stack.push(*self);
189    }
190}
191impl PopFromStack for RawFelt {
192    #[inline(always)]
193    fn try_pop(stack: &mut VecDeque<Felt>) -> Option<Self> {
194        Some(stack.pop_front()?.0)
195    }
196}
197
198impl PushToStack for [RawFelt; 4] {
199    #[inline(always)]
200    fn try_push(&self, stack: &mut Vec<RawFelt>) {
201        stack.extend(self.iter().copied().rev());
202    }
203}
204impl PopFromStack for [RawFelt; 4] {
205    #[inline(always)]
206    fn try_pop(stack: &mut VecDeque<Felt>) -> Option<Self> {
207        let a = stack.pop_front()?;
208        let b = stack.pop_front()?;
209        let c = stack.pop_front()?;
210        let d = stack.pop_front()?;
211        Some([a.0, b.0, c.0, d.0])
212    }
213}
214
215impl PushToStack for Felt {
216    #[inline(always)]
217    fn try_push(&self, stack: &mut Vec<RawFelt>) {
218        stack.push(self.0);
219    }
220}
221impl PopFromStack for Felt {
222    #[inline(always)]
223    fn try_pop(stack: &mut VecDeque<Felt>) -> Option<Self> {
224        stack.pop_front()
225    }
226}
227
228impl PushToStack for [Felt; 4] {
229    #[inline(always)]
230    fn try_push(&self, stack: &mut Vec<RawFelt>) {
231        stack.extend(self.iter().map(|f| f.0).rev());
232    }
233}
234impl PopFromStack for [Felt; 4] {
235    #[inline(always)]
236    fn try_pop(stack: &mut VecDeque<Felt>) -> Option<Self> {
237        let a = stack.pop_front()?;
238        let b = stack.pop_front()?;
239        let c = stack.pop_front()?;
240        let d = stack.pop_front()?;
241        Some([a, b, c, d])
242    }
243}
244
245impl<const N: usize> PopFromStack for [u8; N] {
246    fn try_pop(stack: &mut VecDeque<Felt>) -> Option<Self> {
247        use midenc_hir::FieldElement;
248        let mut out = [0u8; N];
249
250        let chunk_size = (out.len() / 4) + (out.len() % 4 > 0) as usize;
251        for i in 0..chunk_size {
252            let elem: u32 = PopFromStack::try_pop(stack)?;
253            let bytes = elem.to_le_bytes();
254            let offset = i * 4;
255            if offset + 3 < N {
256                out[offset] = bytes[0];
257                out[offset + 1] = bytes[1];
258                out[offset + 2] = bytes[2];
259                out[offset + 3] = bytes[3];
260            } else if offset + 2 < N {
261                out[offset] = bytes[0];
262                out[offset + 1] = bytes[1];
263                out[offset + 2] = bytes[2];
264                break;
265            } else if offset + 1 < N {
266                out[offset] = bytes[0];
267                out[offset + 1] = bytes[1];
268                break;
269            } else if offset < N {
270                out[offset] = bytes[0];
271                break;
272            } else {
273                break;
274            }
275        }
276
277        Some(out)
278    }
279}
280
281/// Convert a byte array to an equivalent vector of words
282///
283/// Given a byte slice laid out like so:
284///
285///     [b0, b1, b2, b3, b4, b5, b6, b7, .., b31]
286///
287/// This will produce a vector of words laid out like so:
288///
289///     [[{b0, ..b3}, {b4, ..b7}, {b8..b11}, {b12, ..b15}], ..]
290///
291/// In other words, it produces words that when placed on the stack and written to memory
292/// word-by-word, that memory will be laid out in the correct byte order.
293pub fn bytes_to_words(bytes: &[u8]) -> Vec<[RawFelt; 4]> {
294    // 1. Chunk bytes up into felts
295    let mut iter = bytes.iter().array_chunks::<4>();
296    let buf_size = (bytes.len() / 4) + (bytes.len() % 4 > 0) as usize;
297    let padding = buf_size % 8;
298    let mut buf = Vec::with_capacity(buf_size + padding);
299    for chunk in iter.by_ref() {
300        let n = u32::from_le_bytes([*chunk[0], *chunk[1], *chunk[2], *chunk[3]]);
301        buf.push(n);
302    }
303    // Zero-pad the buffer to nearest whole element
304    if let Some(rest) = iter.into_remainder() {
305        let mut n_buf = [0u8; 4];
306        for (i, byte) in rest.into_iter().enumerate() {
307            n_buf[i] = *byte;
308        }
309        buf.push(u32::from_le_bytes(n_buf));
310    }
311    // Zero-pad the buffer to nearest whole word
312    let padded_buf_size = buf_size + padding;
313    buf.resize(padded_buf_size, 0);
314    // Chunk into words, and push them in largest-address first order
315    let word_size = (padded_buf_size / 4) + (padded_buf_size % 4 > 0) as usize;
316    let mut words = Vec::with_capacity(word_size);
317    for mut word_chunk in buf.into_iter().map(|elem| RawFelt::new(elem as u64)).array_chunks::<4>()
318    {
319        words.push(word_chunk);
320    }
321    words
322}
323
324/// Wrapper around `miden_processor::Felt` that implements useful traits that are not implemented
325/// for that type.
326#[derive(Debug, Copy, Clone, PartialEq, Eq)]
327pub struct Felt(pub RawFelt);
328impl Felt {
329    #[inline]
330    pub fn new(value: u64) -> Self {
331        Self(RawFelt::new(value))
332    }
333}
334
335impl<'de> Deserialize<'de> for Felt {
336    fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>
337    where
338        D: serde::Deserializer<'de>,
339    {
340        u64::deserialize(deserializer).and_then(|n| {
341            if n > RawFelt::MODULUS {
342                Err(serde::de::Error::custom(
343                    "invalid field element value: exceeds the field modulus",
344                ))
345            } else {
346                RawFelt::try_from(n).map(Felt).map_err(|err| {
347                    serde::de::Error::custom(format!("invalid field element value: {err}"))
348                })
349            }
350        })
351    }
352}
353
354impl clap::builder::ValueParserFactory for Felt {
355    type Parser = FeltParser;
356
357    fn value_parser() -> Self::Parser {
358        FeltParser
359    }
360}
361
362#[doc(hidden)]
363#[derive(Clone)]
364pub struct FeltParser;
365impl clap::builder::TypedValueParser for FeltParser {
366    type Value = Felt;
367
368    fn parse_ref(
369        &self,
370        _cmd: &clap::Command,
371        _arg: Option<&clap::Arg>,
372        value: &std::ffi::OsStr,
373    ) -> Result<Self::Value, clap::error::Error> {
374        use clap::error::{Error, ErrorKind};
375
376        let value = value.to_str().ok_or_else(|| Error::new(ErrorKind::InvalidUtf8))?.trim();
377        value.parse().map_err(|err| Error::raw(ErrorKind::ValueValidation, err))
378    }
379}
380
381impl core::str::FromStr for Felt {
382    type Err = String;
383
384    fn from_str(s: &str) -> Result<Self, Self::Err> {
385        let value = if let Some(value) = s.strip_prefix("0x") {
386            u64::from_str_radix(value, 16)
387                .map_err(|err| format!("invalid field element value: {err}"))?
388        } else {
389            s.parse::<u64>().map_err(|err| format!("invalid field element value: {err}"))?
390        };
391
392        if value > RawFelt::MODULUS {
393            Err("invalid field element value: exceeds the field modulus".to_string())
394        } else {
395            RawFelt::try_from(value).map(Felt)
396        }
397    }
398}
399
400impl From<Felt> for miden_processor::Felt {
401    fn from(f: Felt) -> Self {
402        f.0
403    }
404}
405
406impl From<bool> for Felt {
407    fn from(b: bool) -> Self {
408        Self(RawFelt::from(b as u32))
409    }
410}
411
412impl From<u8> for Felt {
413    fn from(t: u8) -> Self {
414        Self(t.into())
415    }
416}
417
418impl From<i8> for Felt {
419    fn from(t: i8) -> Self {
420        Self((t as u8).into())
421    }
422}
423
424impl From<i16> for Felt {
425    fn from(t: i16) -> Self {
426        Self((t as u16).into())
427    }
428}
429
430impl From<u16> for Felt {
431    fn from(t: u16) -> Self {
432        Self(t.into())
433    }
434}
435
436impl From<i32> for Felt {
437    fn from(t: i32) -> Self {
438        Self((t as u32).into())
439    }
440}
441
442impl From<u32> for Felt {
443    fn from(t: u32) -> Self {
444        Self(t.into())
445    }
446}
447
448impl From<u64> for Felt {
449    fn from(t: u64) -> Self {
450        Self(RawFelt::new(t))
451    }
452}
453
454impl From<i64> for Felt {
455    fn from(t: i64) -> Self {
456        Self(RawFelt::new(t as u64))
457    }
458}
459
460// Reverse Felt to Rust types conversion
461
462impl From<Felt> for bool {
463    fn from(f: Felt) -> Self {
464        f.0.as_int() != 0
465    }
466}
467
468impl From<Felt> for u8 {
469    fn from(f: Felt) -> Self {
470        f.0.as_int() as u8
471    }
472}
473
474impl From<Felt> for i8 {
475    fn from(f: Felt) -> Self {
476        f.0.as_int() as i8
477    }
478}
479
480impl From<Felt> for u16 {
481    fn from(f: Felt) -> Self {
482        f.0.as_int() as u16
483    }
484}
485
486impl From<Felt> for i16 {
487    fn from(f: Felt) -> Self {
488        f.0.as_int() as i16
489    }
490}
491
492impl From<Felt> for u32 {
493    fn from(f: Felt) -> Self {
494        f.0.as_int() as u32
495    }
496}
497
498impl From<Felt> for i32 {
499    fn from(f: Felt) -> Self {
500        f.0.as_int() as i32
501    }
502}
503
504impl From<Felt> for u64 {
505    fn from(f: Felt) -> Self {
506        f.0.as_int()
507    }
508}
509
510impl From<Felt> for i64 {
511    fn from(f: Felt) -> Self {
512        f.0.as_int() as i64
513    }
514}
515
516impl Arbitrary for Felt {
517    type Parameters = ();
518    type Strategy = BoxedStrategy<Self>;
519
520    fn arbitrary_with(_args: Self::Parameters) -> Self::Strategy {
521        use miden_core::StarkField;
522        (0u64..RawFelt::MODULUS).prop_map(|v| Felt(RawFelt::new(v))).boxed()
523    }
524}
525
526#[cfg(test)]
527mod tests {
528    use std::collections::VecDeque;
529
530    use super::{bytes_to_words, PopFromStack};
531
532    #[test]
533    fn bytes_to_words_test() {
534        let bytes = [
535            1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24,
536            25, 26, 27, 28, 29, 30, 31, 32,
537        ];
538        let words = bytes_to_words(&bytes);
539        assert_eq!(words.len(), 2);
540        assert_eq!(words[0][0].as_int() as u32, u32::from_le_bytes([1, 2, 3, 4]));
541        assert_eq!(words[0][1].as_int() as u32, u32::from_le_bytes([5, 6, 7, 8]));
542        assert_eq!(words[0][2].as_int() as u32, u32::from_le_bytes([9, 10, 11, 12]));
543        assert_eq!(words[0][3].as_int() as u32, u32::from_le_bytes([13, 14, 15, 16]));
544    }
545
546    #[test]
547    fn bytes_from_words_test() {
548        let bytes = [
549            1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24,
550            25, 26, 27, 28, 29, 30, 31, 32,
551        ];
552        let words = bytes_to_words(&bytes);
553        let mut stack = VecDeque::from_iter(words.into_iter().flatten().map(super::Felt));
554        let out: [u8; 32] = PopFromStack::try_pop(&mut stack).unwrap();
555        assert_eq!(&out, &bytes);
556    }
557}
midenc_debug/felt.rs

midenc_debug/
felt.rs
