pathfinder_crypto/algebra/field/
felt.rs

1use std::borrow::Cow;
2use std::error::Error;
3
4use bitvec::order::Msb0;
5use bitvec::slice::BitSlice;
6use bitvec::view::BitView;
7use fake::Dummy;
8
9use crate::algebra::field::montfelt::MontFelt;
10
11/// Starknet Field Element.
12///
13/// A field element is a number 0..p-1 with p=2^{251}+17*2^{192}+1, and it forms
14/// the basic building block of most Starknet interactions.
15#[derive(Clone, Copy, PartialEq, Hash, Eq, PartialOrd, Ord)]
16pub struct Felt([u8; 32]);
17
18const MODULUS_U64: [u64; 4] = [576460752303423505u64, 0, 0, 1];
19
20impl std::fmt::Debug for Felt {
21    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
22        write!(f, "Felt({self})")
23    }
24}
25
26impl std::fmt::Display for Felt {
27    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
28        // 0xABCDEF1234567890
29        write!(f, "0x{self:X}")
30    }
31}
32
33impl std::fmt::LowerHex for Felt {
34    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
35        self.0.iter().try_for_each(|&b| write!(f, "{b:02x}"))
36    }
37}
38
39impl std::fmt::UpperHex for Felt {
40    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
41        self.0.iter().try_for_each(|&b| write!(f, "{b:02X}"))
42    }
43}
44
45impl Default for Felt {
46    fn default() -> Self {
47        Felt::ZERO
48    }
49}
50
51impl<T> Dummy<T> for Felt {
52    fn dummy_with_rng<R: rand::Rng + ?Sized>(_: &T, rng: &mut R) -> Self {
53        let mut bytes = [0u8; 32];
54        rng.fill_bytes(&mut bytes);
55        // Some 252 bit values are fine too but we don't really care here
56        bytes[0] &= 0x03;
57        Self(bytes)
58    }
59}
60
61/// Error returned by [Felt::from_be_bytes] indicating the maximum field value
62/// was exceeded.
63#[derive(Debug, PartialEq, Eq, Clone, Copy)]
64pub struct OverflowError;
65
66impl Error for OverflowError {}
67
68const OVERFLOW_MSG: &str = "The maximum field value was exceeded.";
69
70impl std::fmt::Display for OverflowError {
71    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
72        f.write_str(OVERFLOW_MSG)
73    }
74}
75
76impl Felt {
77    pub const ZERO: Felt = Felt([0u8; 32]);
78    pub const ONE: Felt = Self::from_u64(1);
79
80    /// Return true if the element is zero.
81    pub fn is_zero(&self) -> bool {
82        self == &Felt::ZERO
83    }
84
85    /// Returns the big-endian representation of this [Felt].
86    pub const fn to_be_bytes(self) -> [u8; 32] {
87        self.0
88    }
89
90    /// Returns the little-endian representation of this [Felt].
91    pub fn to_le_bytes(self) -> [u8; 32] {
92        let mut tmp = self.0;
93        tmp.reverse();
94        tmp
95    }
96
97    /// Big-endian representation of this [Felt].
98    pub const fn as_be_bytes(&self) -> &[u8; 32] {
99        &self.0
100    }
101
102    /// Big-endian mutable representation of this [Felt].
103    pub fn as_mut_be_bytes(&mut self) -> &mut [u8; 32] {
104        &mut self.0
105    }
106
107    /// Convenience function which extends [Felt::from_be_bytes] to work with
108    /// slices.
109    pub const fn from_be_slice(bytes: &[u8]) -> Result<Self, OverflowError> {
110        if bytes.len() > 32 {
111            return Err(OverflowError);
112        }
113
114        let mut buf = [0u8; 32];
115        let mut index = 0;
116        loop {
117            if index == bytes.len() {
118                break;
119            }
120            buf[32 - bytes.len() + index] = bytes[index];
121            index += 1;
122        }
123
124        Felt::from_be_bytes(buf)
125    }
126
127    pub fn random<R: rand::Rng>(rng: &mut R) -> Self {
128        let r = MontFelt::random(rng);
129        Felt::from(r)
130    }
131
132    /// Creates a [Felt] from big-endian bytes.
133    ///
134    /// Returns [OverflowError] if not less than the field modulus.
135    pub const fn from_be_bytes(bytes: [u8; 32]) -> Result<Self, OverflowError> {
136        #[rustfmt::skip]
137        let limbs = [
138            u64::from_be_bytes([
139                bytes[0], bytes[1], bytes[2], bytes[3],
140                bytes[4], bytes[5], bytes[6], bytes[7],
141            ]),
142            u64::from_be_bytes([
143                bytes[8], bytes[9], bytes[10], bytes[11],
144                bytes[12], bytes[13], bytes[14], bytes[15],
145            ]),
146            u64::from_be_bytes([
147                bytes[16], bytes[17], bytes[18], bytes[19],
148                bytes[20], bytes[21], bytes[22], bytes[23],
149            ]),
150            u64::from_be_bytes([
151                bytes[24], bytes[25], bytes[26], bytes[27],
152                bytes[28], bytes[29], bytes[30], bytes[31],
153            ]),
154        ];
155
156        // Loop over each word, if all previous are equal and current is less, we are
157        // good.
158        let mut maybe_overflow = true;
159        let mut i = 0;
160        while i < 4 && maybe_overflow {
161            if limbs[i] < MODULUS_U64[i] {
162                maybe_overflow = false;
163            } else if limbs[i] > MODULUS_U64[i] {
164                return Err(OverflowError);
165            }
166            i += 1;
167        }
168        if maybe_overflow {
169            Err(OverflowError)
170        } else {
171            Ok(Felt(bytes))
172        }
173    }
174
175    /// Returns a bit view of the 251 least significant bits in MSB order.
176    pub fn view_bits(&self) -> &BitSlice<u8, Msb0> {
177        &self.0.view_bits()[5..]
178    }
179
180    /// Creates a [Felt] from up-to 251 bits.
181    pub fn from_bits(bits: &BitSlice<u8, Msb0>) -> Result<Self, OverflowError> {
182        if bits.len() > 251 {
183            return Err(OverflowError);
184        }
185
186        let mut bytes = [0u8; 32];
187        bytes.view_bits_mut::<Msb0>()[256 - bits.len()..].copy_from_bitslice(bits);
188
189        Ok(Self(bytes))
190    }
191
192    /// Returns `true` if the value of [`Felt`] is larger than `2^251 - 1`.
193    ///
194    /// Every [`Felt`] that is used to traverse a Merkle-Patricia Tree
195    /// must not exceed 251 bits, since 251 is the height of the tree.
196    pub const fn has_more_than_251_bits(&self) -> bool {
197        self.0[0] & 0b1111_1000 > 0
198    }
199
200    pub const fn from_u64(u: u64) -> Self {
201        const_expect!(
202            Self::from_be_slice(&u.to_be_bytes()),
203            "64 bits is less than 251 bits"
204        )
205    }
206
207    pub const fn from_u128(u: u128) -> Self {
208        const_expect!(
209            Self::from_be_slice(&u.to_be_bytes()),
210            "128 bits is less than 251 bits"
211        )
212    }
213}
214
215macro_rules! const_expect {
216    ($e:expr, $why:expr) => {{
217        match $e {
218            Ok(x) => x,
219            Err(_) => panic!(concat!("Expectation failed: ", $why)),
220        }
221    }};
222}
223
224use const_expect;
225
226use crate::algebra::field::CurveOrderMontFelt;
227
228impl From<u64> for Felt {
229    fn from(value: u64) -> Self {
230        Self::from_u64(value)
231    }
232}
233
234impl From<usize> for Felt {
235    fn from(value: usize) -> Self {
236        Self::from_u64(value.try_into().expect("ptr size is 64 bits"))
237    }
238}
239
240impl From<u128> for Felt {
241    fn from(value: u128) -> Self {
242        Self::from_u128(value)
243    }
244}
245
246impl From<[u8; 32]> for Felt {
247    fn from(bytes: [u8; 32]) -> Self {
248        Self(bytes)
249    }
250}
251
252impl TryInto<u128> for Felt {
253    type Error = OverflowError;
254
255    fn try_into(self) -> Result<u128, Self::Error> {
256        let initial_zeroes = self.0.iter().take_while(|b| **b == 0).count();
257        const EXPECTED_ZEROES: usize = (32 - u128::BITS / u8::BITS) as usize;
258
259        if initial_zeroes < EXPECTED_ZEROES {
260            return Err(OverflowError);
261        }
262
263        let bytes = self.0[EXPECTED_ZEROES..]
264            .try_into()
265            .expect("Should match u128 size");
266        Ok(u128::from_be_bytes(bytes))
267    }
268}
269
270impl TryInto<u64> for Felt {
271    type Error = OverflowError;
272
273    fn try_into(self) -> Result<u64, Self::Error> {
274        let initial_zeroes = self.0.iter().take_while(|b| **b == 0).count();
275        const EXPECTED_ZEROES: usize = (32 - u64::BITS / u8::BITS) as usize;
276
277        if initial_zeroes < EXPECTED_ZEROES {
278            return Err(OverflowError);
279        }
280        let bytes = self.0[EXPECTED_ZEROES..]
281            .try_into()
282            .expect("Should match u64 size");
283        Ok(u64::from_be_bytes(bytes))
284    }
285}
286
287impl std::ops::Add for Felt {
288    type Output = Felt;
289
290    fn add(self, rhs: Self) -> Self::Output {
291        let result = MontFelt::from(self) + MontFelt::from(rhs);
292        Felt::from(result)
293    }
294}
295
296impl std::ops::Sub for Felt {
297    type Output = Felt;
298
299    fn sub(self, rhs: Self) -> Self::Output {
300        let result = MontFelt::from(self) - MontFelt::from(rhs);
301        Felt::from(result)
302    }
303}
304
305impl From<MontFelt> for Felt {
306    fn from(fp: MontFelt) -> Self {
307        // safe as BE-bytes representations are the same
308        debug_assert_eq!(std::mem::size_of::<MontFelt>(), std::mem::size_of::<Felt>());
309        let bytes: [u8; 32] = fp.to_be_bytes();
310        Felt::from_be_bytes(bytes).unwrap()
311    }
312}
313
314impl From<CurveOrderMontFelt> for Felt {
315    fn from(value: CurveOrderMontFelt) -> Self {
316        // safe as BE-bytes representations are the same
317        debug_assert_eq!(std::mem::size_of::<MontFelt>(), std::mem::size_of::<Felt>());
318        let bytes = value.to_be_bytes();
319        Felt::from_be_bytes(bytes).unwrap()
320    }
321}
322
323impl Felt {
324    /// A convenience function which parses a hex string into a [Felt].
325    ///
326    /// Supports both upper and lower case hex strings, as well as an optional
327    /// "0x" prefix.
328    pub const fn from_hex_str(hex_str: &str) -> Result<Self, HexParseError> {
329        const fn parse_hex_digit(digit: u8) -> Result<u8, HexParseError> {
330            match digit {
331                b'0'..=b'9' => Ok(digit - b'0'),
332                b'A'..=b'F' => Ok(digit - b'A' + 10),
333                b'a'..=b'f' => Ok(digit - b'a' + 10),
334                other => Err(HexParseError::InvalidNibble(other)),
335            }
336        }
337
338        let bytes = hex_str.as_bytes();
339        let start = if bytes.len() >= 2 && bytes[0] == b'0' && bytes[1] == b'x' {
340            2
341        } else {
342            0
343        };
344        let len = bytes.len() - start;
345
346        if len > 64 {
347            return Err(HexParseError::InvalidLength {
348                max: 64,
349                actual: bytes.len(),
350            });
351        }
352
353        let mut buf = [0u8; 32];
354
355        // We want the result in big-endian so reverse iterate over each pair of
356        // nibbles. let chunks = hex_str.as_bytes().rchunks_exact(2);
357
358        // Handle a possible odd nibble remaining nibble.
359        if len % 2 == 1 {
360            let idx = len / 2;
361            buf[31 - idx] = match parse_hex_digit(bytes[start]) {
362                Ok(b) => b,
363                Err(e) => return Err(e),
364            };
365        }
366
367        let chunks = len / 2;
368        let mut chunk = 0;
369
370        while chunk < chunks {
371            let lower = match parse_hex_digit(bytes[bytes.len() - chunk * 2 - 1]) {
372                Ok(b) => b,
373                Err(e) => return Err(e),
374            };
375            let upper = match parse_hex_digit(bytes[bytes.len() - chunk * 2 - 2]) {
376                Ok(b) => b,
377                Err(e) => return Err(e),
378            };
379            buf[31 - chunk] = (upper << 4) | lower;
380            chunk += 1;
381        }
382
383        let felt = match Felt::from_be_bytes(buf) {
384            Ok(felt) => felt,
385            Err(OverflowError) => return Err(HexParseError::Overflow),
386        };
387        Ok(felt)
388    }
389
390    /// The first stage of conversion - skip leading zeros
391    fn skip_zeros(&self) -> (impl Iterator<Item = &u8>, usize, usize) {
392        // Skip all leading zero bytes
393        let it = self.0.iter().skip_while(|&&b| b == 0);
394        let num_bytes = it.clone().count();
395        let skipped = self.0.len() - num_bytes;
396        // The first high nibble can be 0
397        let start = if self.0[skipped] < 0x10 { 1 } else { 2 };
398        // Number of characters to display
399        let len = start + num_bytes * 2;
400        (it, start, len)
401    }
402
403    /// The second stage of conversion - map bytes to hex str
404    fn it_to_hex_str<'a>(
405        it: impl Iterator<Item = &'a u8>,
406        start: usize,
407        len: usize,
408        buf: &'a mut [u8],
409    ) -> &'a [u8] {
410        const LUT: [u8; 16] = *b"0123456789abcdef";
411        buf[0] = b'0';
412        // Same small lookup table is ~25% faster than hex::encode_from_slice 🤷
413        it.enumerate().for_each(|(i, &b)| {
414            let idx = b as usize;
415            let pos = start + i * 2;
416            let x = [LUT[(idx & 0xf0) >> 4], LUT[idx & 0x0f]];
417            buf[pos..pos + 2].copy_from_slice(&x);
418        });
419        buf[1] = b'x';
420        &buf[..len]
421    }
422
423    /// A convenience function which produces a "0x" prefixed hex str slice in a
424    /// given buffer `buf` from a [Felt].
425    /// Panics if `self.0.len() * 2 + 2 > buf.len()`
426    pub fn as_hex_str<'a>(&'a self, buf: &'a mut [u8]) -> &'a str {
427        let expected_buf_len = self.0.len() * 2 + 2;
428        assert!(
429            buf.len() >= expected_buf_len,
430            "buffer size is {}, expected at least {}",
431            buf.len(),
432            expected_buf_len
433        );
434
435        if !self.0.iter().any(|b| *b != 0) {
436            return "0x0";
437        }
438
439        let (it, start, len) = self.skip_zeros();
440        let res = Self::it_to_hex_str(it, start, len, buf);
441        // Unwrap is safe because `buf` holds valid UTF8 characters.
442        std::str::from_utf8(res).unwrap()
443    }
444
445    /// A convenience function which produces a "0x" prefixed hex string from a
446    /// [Felt].
447    pub fn to_hex_str(&self) -> Cow<'static, str> {
448        if !self.0.iter().any(|b| *b != 0) {
449            return Cow::from("0x0");
450        }
451        let (it, start, len) = self.skip_zeros();
452        let mut buf = vec![0u8; len];
453        Self::it_to_hex_str(it, start, len, &mut buf);
454        // Unwrap is safe as the buffer contains valid utf8
455        String::from_utf8(buf).unwrap().into()
456    }
457}
458
459/// Error returned by [Felt::from_hex_str] indicating an invalid hex string.
460#[derive(Debug, PartialEq, Eq)]
461pub enum HexParseError {
462    InvalidNibble(u8),
463    InvalidLength { max: usize, actual: usize },
464    Overflow,
465}
466
467impl Error for HexParseError {}
468
469impl From<OverflowError> for HexParseError {
470    fn from(_: OverflowError) -> Self {
471        Self::Overflow
472    }
473}
474
475impl std::fmt::Display for HexParseError {
476    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
477        match self {
478            Self::InvalidNibble(n) => f.write_fmt(format_args!("Invalid nibble found: 0x{:x}", *n)),
479            Self::InvalidLength { max, actual } => {
480                f.write_fmt(format_args!("More than {} digits found: {}", *max, *actual))
481            }
482            Self::Overflow => f.write_str(OVERFLOW_MSG),
483        }
484    }
485}
486
487#[cfg(test)]
488mod tests {
489    use bitvec::bitvec;
490    use pretty_assertions_sorted::assert_eq;
491
492    use super::*;
493
494    const MODULUS_U8: [u8; 32] = [
495        8, 0, 0, 0, 0, 0, 0, 17, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
496        0, 1,
497    ];
498
499    #[test]
500    fn view_bits() {
501        let one = Felt::from_hex_str("1").unwrap();
502
503        let one = one.view_bits().to_bitvec();
504
505        let mut expected = bitvec![0; 251];
506        expected.set(250, true);
507        assert_eq!(one, expected);
508    }
509
510    #[test]
511    fn bits_round_trip() {
512        let mut bits = bitvec![u8, Msb0; 1; 251];
513        bits.set(0, false);
514        bits.set(1, false);
515        bits.set(2, false);
516        bits.set(3, false);
517        bits.set(4, false);
518
519        let res = Felt::from_bits(&bits).unwrap();
520
521        let x = res.view_bits();
522        let y = Felt::from_bits(x).unwrap();
523
524        assert_eq!(res, y);
525    }
526
527    #[test]
528    fn bytes_round_trip() {
529        let original = [
530            0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07, 0x08, 0x09, 0x0A, 0x0B, 0x0C, 0x0D,
531            0x0E, 0x0F, 0x10, 0x11, 0x12, 0x13, 0x14, 0x15, 0x16, 0x17, 0x18, 0x19, 0x1A, 0x1B,
532            0x1C, 0x1D, 0x1E, 0x1F,
533        ];
534        let hash = Felt::from_be_bytes(original).unwrap();
535        let bytes = hash.to_be_bytes();
536        assert_eq!(bytes, original);
537    }
538
539    #[test]
540    fn from_bytes_overflow() {
541        // Field modulus
542        assert_eq!(Felt::from_be_bytes(MODULUS_U8), Err(OverflowError));
543        // Field modulus - 1
544        let mut max_val = MODULUS_U8;
545        max_val[31] -= 1;
546        Felt::from_be_bytes(max_val).unwrap();
547    }
548
549    #[test]
550    fn field_round_trip() {
551        let bytes = [
552            0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07, 0x08, 0x09, 0x0A, 0x0B, 0x0C, 0x0D,
553            0x0E, 0x0F, 0x10, 0x11, 0x12, 0x13, 0x14, 0x15, 0x16, 0x17, 0x18, 0x19, 0x1A, 0x1B,
554            0x1C, 0x1D, 0x1E, 0x1F,
555        ];
556        let original = Felt::from_be_bytes(bytes).unwrap();
557        let fp = MontFelt::from(original);
558        let hash = Felt::from(fp);
559        assert_eq!(hash, original);
560    }
561
562    mod from_be_slice {
563        use pretty_assertions_sorted::assert_eq;
564
565        use super::*;
566
567        #[test]
568        fn round_trip() {
569            let original = Felt::from_hex_str("abcdef0123456789").unwrap();
570            let bytes = original.to_be_bytes();
571            let result = Felt::from_be_slice(&bytes[..]).unwrap();
572
573            assert_eq!(result, original);
574        }
575
576        #[test]
577        fn too_long() {
578            let original = Felt::from_hex_str("abcdef0123456789").unwrap();
579            let mut bytes = original.to_be_bytes().to_vec();
580            bytes.push(0);
581            Felt::from_be_slice(&bytes[..]).unwrap_err();
582        }
583
584        #[test]
585        fn short_slice() {
586            let original = Felt::from_hex_str("abcdef0123456789").unwrap();
587            let bytes = original.to_be_bytes();
588            let result = Felt::from_be_slice(&bytes[24..]);
589
590            assert_eq!(result, Ok(original));
591        }
592
593        #[test]
594        fn max() {
595            let mut max_val = MODULUS_U8;
596            max_val[31] -= 1;
597            Felt::from_be_slice(&max_val[..]).unwrap();
598        }
599
600        #[test]
601        fn overflow() {
602            assert_eq!(Felt::from_be_slice(&MODULUS_U8[..]), Err(OverflowError));
603        }
604    }
605
606    mod fmt {
607        use pretty_assertions_sorted::assert_eq;
608
609        use super::Felt;
610
611        #[test]
612        fn debug() {
613            let hex_str = "1234567890abcdef000edcba0987654321";
614            let felt = Felt::from_hex_str(hex_str).unwrap();
615            let result = format!("{felt:?}");
616
617            let mut expected = "0".repeat(64 - hex_str.len());
618            expected.push_str(hex_str);
619            let expected = format!("Felt({felt})");
620
621            assert_eq!(result, expected);
622        }
623
624        #[test]
625        fn fmt() {
626            let hex_str = "1234567890abcdef000edcba0987654321";
627            let starkhash = Felt::from_hex_str(hex_str).unwrap();
628            let result = format!("{starkhash:x}");
629
630            let mut expected = "0".repeat(64 - hex_str.len());
631            expected.push_str(hex_str);
632
633            // We don't really care which casing is used by fmt.
634            assert_eq!(result.to_lowercase(), expected.to_lowercase());
635        }
636
637        #[test]
638        fn lower_hex() {
639            let hex_str = "1234567890abcdef000edcba0987654321";
640            let starkhash = Felt::from_hex_str(hex_str).unwrap();
641            let result = format!("{starkhash:x}");
642
643            let mut expected = "0".repeat(64 - hex_str.len());
644            expected.push_str(hex_str);
645
646            assert_eq!(result, expected.to_lowercase());
647        }
648
649        #[test]
650        fn upper_hex() {
651            let hex_str = "1234567890abcdef000edcba0987654321";
652            let starkhash = Felt::from_hex_str(hex_str).unwrap();
653            let result = format!("{starkhash:X}");
654
655            let mut expected = "0".repeat(64 - hex_str.len());
656            expected.push_str(hex_str);
657
658            assert_eq!(result, expected.to_uppercase());
659        }
660    }
661
662    mod from_hex_str {
663        use assert_matches::assert_matches;
664        use pretty_assertions_sorted::assert_eq;
665
666        use super::*;
667
668        /// Test hex string with its expected [Felt].
669        fn test_data() -> (&'static str, Felt) {
670            let mut expected = [0; 32];
671            expected[31] = 0xEF;
672            expected[30] = 0xCD;
673            expected[29] = 0xAB;
674            expected[28] = 0xef;
675            expected[27] = 0xcd;
676            expected[26] = 0xab;
677            expected[25] = 0x89;
678            expected[24] = 0x67;
679            expected[23] = 0x45;
680            expected[22] = 0x23;
681            expected[21] = 0x01;
682            let expected = Felt::from_be_bytes(expected).unwrap();
683
684            ("0123456789abcdefABCDEF", expected)
685        }
686
687        #[test]
688        fn simple() {
689            let (test_str, expected) = test_data();
690            let uut = Felt::from_hex_str(test_str).unwrap();
691            assert_eq!(uut, expected);
692        }
693
694        #[test]
695        fn prefix() {
696            let (test_str, expected) = test_data();
697            let uut = Felt::from_hex_str(&format!("0x{test_str}")).unwrap();
698            assert_eq!(uut, expected);
699        }
700
701        #[test]
702        fn leading_zeros() {
703            let (test_str, expected) = test_data();
704            let uut = Felt::from_hex_str(&format!("000000000{test_str}")).unwrap();
705            assert_eq!(uut, expected);
706        }
707
708        #[test]
709        fn prefix_and_leading_zeros() {
710            let (test_str, expected) = test_data();
711            let uut = Felt::from_hex_str(&format!("0x000000000{test_str}")).unwrap();
712            assert_eq!(uut, expected);
713        }
714
715        #[test]
716        fn invalid_nibble() {
717            assert_matches!(Felt::from_hex_str("0x123z").unwrap_err(), HexParseError::InvalidNibble(n) => assert_eq!(n, b'z'))
718        }
719
720        #[test]
721        fn invalid_len() {
722            assert_matches!(Felt::from_hex_str(&"1".repeat(65)).unwrap_err(), HexParseError::InvalidLength{max: 64, actual: n} => assert_eq!(n, 65))
723        }
724
725        #[test]
726        fn overflow() {
727            // Field modulus
728            let mut modulus =
729                "0x800000000000011000000000000000000000000000000000000000000000001".to_string();
730            assert_eq!(
731                Felt::from_hex_str(&modulus).unwrap_err(),
732                HexParseError::Overflow
733            );
734            // Field modulus - 1
735            modulus.pop();
736            modulus.push('0');
737            Felt::from_hex_str(&modulus).unwrap();
738        }
739    }
740
741    mod to_hex_str {
742        use pretty_assertions_sorted::assert_eq;
743
744        use super::*;
745
746        const ODD: &str = "0x1234567890abcde";
747        const EVEN: &str = "0x1234567890abcdef";
748        const MAX: &str = "0x800000000000011000000000000000000000000000000000000000000000000";
749
750        #[test]
751        fn zero() {
752            assert_eq!(Felt::ZERO.to_hex_str(), "0x0");
753            let mut buf = [0u8; 66];
754            assert_eq!(Felt::ZERO.as_hex_str(&mut buf), "0x0");
755        }
756
757        #[test]
758        fn odd() {
759            let hash = Felt::from_hex_str(ODD).unwrap();
760            assert_eq!(hash.to_hex_str(), ODD);
761            let mut buf = [0u8; 66];
762            assert_eq!(hash.as_hex_str(&mut buf), ODD);
763        }
764
765        #[test]
766        fn even() {
767            let hash = Felt::from_hex_str(EVEN).unwrap();
768            assert_eq!(hash.to_hex_str(), EVEN);
769            let mut buf = [0u8; 66];
770            assert_eq!(hash.as_hex_str(&mut buf), EVEN);
771        }
772
773        #[test]
774        fn max() {
775            let hash = Felt::from_hex_str(MAX).unwrap();
776            assert_eq!(hash.to_hex_str(), MAX);
777            let mut buf = [0u8; 66];
778            assert_eq!(hash.as_hex_str(&mut buf), MAX);
779        }
780
781        #[test]
782        #[should_panic]
783        fn buffer_too_small() {
784            let mut buf = [0u8; 65];
785            Felt::ZERO.as_hex_str(&mut buf);
786        }
787    }
788
789    mod has_more_than_251_bits {
790        use super::*;
791
792        #[test]
793        fn has_251_bits() {
794            let mut bytes = [0xFFu8; 32];
795            bytes[0] = 0x07;
796            let h = Felt::from_be_bytes(bytes).unwrap();
797            assert!(!h.has_more_than_251_bits());
798        }
799
800        #[test]
801        fn has_252_bits() {
802            let mut bytes = [0u8; 32];
803            bytes[0] = 0x08;
804            let h = Felt::from_be_bytes(bytes).unwrap();
805            assert!(h.has_more_than_251_bits());
806        }
807    }
808}
pathfinder_crypto/algebra/field/felt.rs

pathfinder_crypto/algebra/field/
felt.rs
