acir_field/
field_element.rs

1use ark_ff::PrimeField;
2use ark_ff::Zero;
3use msgpack_tagged::MsgpackTagged;
4use num_bigint::BigUint;
5use serde::{Deserialize, Serialize};
6use std::ops::{Add, AddAssign, Div, Mul, Neg, Sub, SubAssign};
7
8use crate::AcirField;
9
10/// The value 2^127, which represents the boundary between positive and negative
11/// values in i128 representation. Values greater this are treated as negative when
12/// converting to signed integers.
13const I128_SIGN_BOUNDARY: u128 = 1_u128 << 127;
14
15// XXX: Include a trait-based design with field-specific implementations.
16#[derive(Default, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
17pub struct FieldElement<F: PrimeField>(F);
18
19impl<F: PrimeField> std::fmt::Display for FieldElement<F> {
20    fn fmt(&self, f: &mut std::fmt::Formatter) -> std::fmt::Result {
21        // First check if the number is zero
22        //
23        let number = BigUint::from_bytes_be(&self.to_be_bytes());
24        if number == BigUint::zero() {
25            return write!(f, "0");
26        }
27        // Check if the negative version is smaller to represent
28        //
29        let minus_number = BigUint::from_bytes_be(&(self.neg()).to_be_bytes());
30        let (smaller_repr, is_negative) =
31            if minus_number.to_string().len() < number.to_string().len() {
32                (minus_number, true)
33            } else {
34                (number, false)
35            };
36        if is_negative {
37            write!(f, "-")?;
38        }
39
40        write!(f, "{smaller_repr}")
41    }
42}
43
44impl<F: PrimeField> std::fmt::Debug for FieldElement<F> {
45    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
46        std::fmt::Display::fmt(self, f)
47    }
48}
49
50impl<F: PrimeField> From<i128> for FieldElement<F> {
51    fn from(a: i128) -> FieldElement<F> {
52        // Optimized: Convert directly without string conversion
53        if a >= 0 {
54            // Positive case: convert via u128
55            FieldElement(F::from(a as u128))
56        } else {
57            // Negative case: handle i128::MIN specially to avoid overflow
58            let abs_value = a.wrapping_neg() as u128;
59            FieldElement(-F::from(abs_value))
60        }
61    }
62}
63
64impl<F: PrimeField> From<i64> for FieldElement<F> {
65    fn from(a: i64) -> Self {
66        // Optimized: Convert directly without string conversion
67        if a >= 0 {
68            FieldElement(F::from(a as u64))
69        } else {
70            // Negative case: handle i64::MIN specially to avoid overflow
71            let abs_value = a.wrapping_neg() as u64;
72            FieldElement(-F::from(abs_value))
73        }
74    }
75}
76
77impl<F: PrimeField> From<i32> for FieldElement<F> {
78    fn from(a: i32) -> Self {
79        // Optimized: Convert directly without string conversion
80        if a >= 0 {
81            FieldElement(F::from(a as u32))
82        } else {
83            // Negative case: handle i32::MIN specially to avoid overflow
84            let abs_value = a.wrapping_neg() as u32;
85            FieldElement(-F::from(abs_value))
86        }
87    }
88}
89
90impl<F: PrimeField> From<i16> for FieldElement<F> {
91    fn from(a: i16) -> Self {
92        // Optimized: Convert directly without string conversion
93        if a >= 0 {
94            FieldElement(F::from(a as u16))
95        } else {
96            // Negative case: handle i16::MIN specially to avoid overflow
97            let abs_value = a.wrapping_neg() as u16;
98            FieldElement(-F::from(abs_value))
99        }
100    }
101}
102
103impl<F: PrimeField> From<i8> for FieldElement<F> {
104    fn from(a: i8) -> Self {
105        // Optimized: Convert directly without string conversion
106        if a >= 0 {
107            FieldElement(F::from(a as u8))
108        } else {
109            // Negative case: handle i8::MIN specially to avoid overflow
110            let abs_value = a.wrapping_neg() as u8;
111            FieldElement(-F::from(abs_value))
112        }
113    }
114}
115
116impl<T: PrimeField> Serialize for FieldElement<T> {
117    fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>
118    where
119        S: serde::Serializer,
120    {
121        // Call `serialize_bytes` rather than `self.to_be_bytes().serialize(...)`
122        // (which would forward to `Vec<u8>::serialize` and then
123        // `serializer.collect_seq(...)`). A field element is
124        // semantically a fixed-width byte blob, not a sequence of u8
125        // elements, and going through `serialize_bytes` keeps the wire
126        // shape consistent across serializers:
127        //
128        // * `rmp_serde`'s `serialize_bytes` is unconditional
129        //   `write_bin` — independent of `BytesMode` — so all three
130        //   `Format::Msgpack*` variants emit the same `bin` blob the
131        //   C++ codegen's `std::vector<uint8_t>` adapter expects.
132        // * Without this, our `MsgpackTagged` wrapper would have to intercept
133        //   the `collect_seq` call and emit a `fixarray` of `fixint`s
134        //   instead (per its tagged-recursion contract for sequences),
135        //   which msgpack-c's `std::vector<uint8_t>` adapter refuses
136        //   with `type_error` mid-decode — a confusing failure mode
137        //   that's much easier to land in than to debug. The other two
138        //   `Msgpack*` formats would have to remember to create a
139        //   `RmpSerializer::with_bytes(BytesMode::ForceAll)`.
140        //
141        // The corresponding `Deserialize` (see below) calls
142        // `deserialize_bytes` via a visitor — the symmetric read hook.
143        serializer.serialize_bytes(&self.to_be_bytes())
144    }
145}
146
147impl<'de, T: PrimeField> Deserialize<'de> for FieldElement<T> {
148    fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>
149    where
150        D: serde::Deserializer<'de>,
151    {
152        // Mirror of `Serialize`: route explicitly through the bytes
153        // hook (`deserialize_byte_buf` under the covers) so the read
154        // side is symmetric with the write side and matches the
155        // msgpack `bin` shape `FieldElement::serialize` emits.
156        // `serde_bytes::ByteBuf` is serde-ecosystem's standard wrapper
157        // for "deserialize as bytes, give me an owned `Vec<u8>`",
158        // wrapping the same visitor boilerplate a hand-rolled one
159        // would. The default `Vec<u8>::deserialize` would instead
160        // route to `deserialize_seq` and reject `bin` under our
161        // `MsgpackTagged` wrapper.
162        let bytes = serde_bytes::ByteBuf::deserialize(deserializer)?;
163        Ok(Self::from_be_bytes_reduce(&bytes))
164    }
165}
166
167impl<F: PrimeField> From<u128> for FieldElement<F> {
168    fn from(a: u128) -> FieldElement<F> {
169        FieldElement(F::from(a))
170    }
171}
172
173impl<F: PrimeField> From<usize> for FieldElement<F> {
174    fn from(a: usize) -> FieldElement<F> {
175        FieldElement::from(a as u64)
176    }
177}
178
179impl<F: PrimeField> From<u64> for FieldElement<F> {
180    fn from(a: u64) -> FieldElement<F> {
181        FieldElement(F::from(a))
182    }
183}
184
185impl<F: PrimeField> From<u32> for FieldElement<F> {
186    fn from(a: u32) -> FieldElement<F> {
187        FieldElement(F::from(a))
188    }
189}
190
191impl<F: PrimeField> From<u16> for FieldElement<F> {
192    fn from(a: u16) -> FieldElement<F> {
193        FieldElement(F::from(a))
194    }
195}
196
197impl<F: PrimeField> From<u8> for FieldElement<F> {
198    fn from(a: u8) -> FieldElement<F> {
199        FieldElement(F::from(a))
200    }
201}
202
203impl<F: PrimeField> From<bool> for FieldElement<F> {
204    fn from(boolean: bool) -> FieldElement<F> {
205        if boolean { FieldElement::one() } else { FieldElement::zero() }
206    }
207}
208
209impl<F: PrimeField> TryFrom<FieldElement<F>> for u128 {
210    type Error = ();
211
212    fn try_from(value: FieldElement<F>) -> Result<Self, Self::Error> {
213        value.try_into_u128().ok_or(())
214    }
215}
216
217impl<F: PrimeField> TryFrom<FieldElement<F>> for u64 {
218    type Error = ();
219
220    fn try_from(value: FieldElement<F>) -> Result<Self, Self::Error> {
221        value.try_to_u64().ok_or(())
222    }
223}
224
225impl<F: PrimeField> TryFrom<FieldElement<F>> for u32 {
226    type Error = ();
227
228    fn try_from(value: FieldElement<F>) -> Result<Self, Self::Error> {
229        value.try_to_u32().ok_or(())
230    }
231}
232
233impl<F: PrimeField> TryFrom<FieldElement<F>> for u16 {
234    type Error = ();
235
236    fn try_from(value: FieldElement<F>) -> Result<Self, Self::Error> {
237        value.try_to_u32().and_then(|x| x.try_into().ok()).ok_or(())
238    }
239}
240
241impl<F: PrimeField> TryFrom<FieldElement<F>> for u8 {
242    type Error = ();
243
244    fn try_from(value: FieldElement<F>) -> Result<Self, Self::Error> {
245        value.try_to_u32().and_then(|x| x.try_into().ok()).ok_or(())
246    }
247}
248
249impl<F: PrimeField> TryFrom<FieldElement<F>> for i128 {
250    type Error = ();
251
252    fn try_from(value: FieldElement<F>) -> Result<Self, Self::Error> {
253        value.try_into_i128().ok_or(())
254    }
255}
256
257impl<F: PrimeField> TryFrom<FieldElement<F>> for i64 {
258    type Error = ();
259
260    fn try_from(value: FieldElement<F>) -> Result<Self, Self::Error> {
261        value.try_into_i128().and_then(|x| x.try_into().ok()).ok_or(())
262    }
263}
264
265impl<F: PrimeField> TryFrom<FieldElement<F>> for i32 {
266    type Error = ();
267
268    fn try_from(value: FieldElement<F>) -> Result<Self, Self::Error> {
269        value.try_into_i128().and_then(|x| x.try_into().ok()).ok_or(())
270    }
271}
272
273impl<F: PrimeField> TryFrom<FieldElement<F>> for i16 {
274    type Error = ();
275
276    fn try_from(value: FieldElement<F>) -> Result<Self, Self::Error> {
277        value.try_into_i128().and_then(|x| x.try_into().ok()).ok_or(())
278    }
279}
280
281impl<F: PrimeField> TryFrom<FieldElement<F>> for i8 {
282    type Error = ();
283
284    fn try_from(value: FieldElement<F>) -> Result<Self, Self::Error> {
285        value.try_into_i128().and_then(|x| x.try_into().ok()).ok_or(())
286    }
287}
288
289impl<F: PrimeField> From<FieldElement<F>> for bool {
290    fn from(field: FieldElement<F>) -> bool {
291        !field.is_zero()
292    }
293}
294
295impl<F: PrimeField> FieldElement<F> {
296    /// Constructs a `FieldElement` from the underlying prime field representation.
297    ///
298    /// This wraps an `ark_ff::PrimeField` element into a `FieldElement`.
299    pub fn from_repr(field: F) -> Self {
300        Self(field)
301    }
302
303    /// Extracts the underlying prime field representation.
304    ///
305    /// This returns the wrapped `ark_ff::PrimeField` element.
306    pub fn into_repr(self) -> F {
307        self.0
308    }
309
310    /// Returns true if this field element can be represented as a u128.
311    ///
312    /// A field element fits in u128 if it requires at most 128 bits to represent,
313    /// i.e., if its value is in the range [0, 2^128 - 1].
314    pub fn fits_in_u128(&self) -> bool {
315        self.num_bits() <= 128
316    }
317
318    /// Returns true if this field element can be represented as an i128.
319    ///
320    /// An i128 can represent values in the range [i128::MIN, i128::MAX], which corresponds
321    /// to field elements in [0, 2^127 - 1] (positive) and [p - 2^127, p - 1] (negative),
322    /// where p is the field modulus. The positive value 2^127 does not fit (it exceeds
323    /// i128::MAX), but the field element representing -2^127 (i.e. p - 2^127) does fit
324    /// (it is i128::MIN).
325    pub fn fits_in_i128(&self) -> bool {
326        let neg = self.neg();
327        self.num_bits() <= 127
328            || neg.num_bits() <= 127
329            || self.neg() == FieldElement::from(I128_SIGN_BOUNDARY)
330    }
331
332    /// Returns None, if the string is not a canonical
333    /// representation of a field element; less than the order
334    /// or if the hex string is invalid.
335    /// This method can be used for both hex and decimal representations.
336    pub fn try_from_str(input: &str) -> Option<FieldElement<F>> {
337        if input.contains('x') {
338            return FieldElement::from_hex(input);
339        }
340
341        let fr = F::from_str(input).ok()?;
342        Some(FieldElement(fr))
343    }
344
345    /// Assume this field element holds a signed integer of the given `bit_size` and format
346    /// it as a string. The range of valid values for this field element is `0..2^bit_size`
347    /// with `0..2^(bit_size - 1)` representing positive values and `2^(bit_size - 1)..2^bit_size`
348    /// representing negative values (as is commonly done for signed integers).
349    /// `2^(bit_size - 1)` is the lowest negative value, so for example if bit_size is 8 then
350    /// `0..127` map to `0..127`, `128` maps to `-128`, `129` maps to `-127` and `255` maps to `-1`.
351    /// If `self` falls outside of the valid range it's formatted as-is.
352    pub fn to_string_as_signed_integer(self, bit_size: u32) -> String {
353        assert!(bit_size <= 128);
354        if self.num_bits() > bit_size {
355            return self.to_string();
356        }
357
358        // Compute the maximum value that is considered a positive value
359        let max = if bit_size == 128 { i128::MAX as u128 } else { (1 << (bit_size - 1)) - 1 };
360        if self.to_u128() > max {
361            let f = FieldElement::from(2u32).pow(&bit_size.into()) - self;
362            format!("-{f}")
363        } else {
364            self.to_string()
365        }
366    }
367}
368
369impl<F: PrimeField> AcirField for FieldElement<F> {
370    fn one() -> FieldElement<F> {
371        FieldElement(F::one())
372    }
373    fn zero() -> FieldElement<F> {
374        FieldElement(F::zero())
375    }
376
377    fn is_zero(&self) -> bool {
378        self == &Self::zero()
379    }
380    fn is_one(&self) -> bool {
381        self == &Self::one()
382    }
383
384    fn pow(&self, exponent: &Self) -> Self {
385        FieldElement(self.0.pow(exponent.0.into_bigint()))
386    }
387
388    /// Maximum number of bits needed to represent a field element
389    /// This is not the amount of bits being used to represent a field element
390    /// Example, you only need 254 bits to represent a field element in BN256
391    /// But the representation uses 256 bits, so the top two bits are always zero
392    /// This method would return 254
393    fn max_num_bits() -> u32 {
394        F::MODULUS_BIT_SIZE
395    }
396
397    /// Maximum numbers of bytes needed to represent a field element
398    /// We are not guaranteed that the number of bits being used to represent a field element
399    /// will always be divisible by 8. If the case that it is not, we add one to the max number of bytes
400    /// For example, a max bit size of 254 would give a max byte size of 32.
401    fn max_num_bytes() -> u32 {
402        let num_bytes = Self::max_num_bits() / 8;
403        if Self::max_num_bits() % 8 == 0 { num_bytes } else { num_bytes + 1 }
404    }
405
406    fn modulus() -> BigUint {
407        F::MODULUS.into()
408    }
409
410    /// This is the number of bits required to represent this specific field element
411    fn num_bits(&self) -> u32 {
412        let bigint = self.0.into_bigint();
413        let limbs = bigint.as_ref();
414        for (i, &limb) in limbs.iter().enumerate().rev() {
415            if limb != 0 {
416                return (i as u32) * 64 + (64 - limb.leading_zeros());
417            }
418        }
419        0
420    }
421
422    fn to_u128(self) -> u128 {
423        if !self.fits_in_u128() {
424            panic!("field element too large for u128");
425        }
426        let as_bigint = self.0.into_bigint();
427        let limbs = as_bigint.as_ref();
428
429        let mut result = u128::from(limbs[0]);
430        if limbs.len() > 1 {
431            let high_limb = u128::from(limbs[1]);
432            result += high_limb << 64;
433        }
434
435        result
436    }
437
438    fn try_into_u128(self) -> Option<u128> {
439        self.fits_in_u128().then(|| self.to_u128())
440    }
441
442    fn to_i128(self) -> i128 {
443        if !self.fits_in_i128() {
444            panic!("field element too large for i128");
445        }
446        // Negative integers are represented by the range [p + i128::MIN, p) while
447        // positive integers are represented by the range [0, i128::MAX).
448        // We can then differentiate positive from negative values by their MSB.
449        if self.neg().num_bits() < self.num_bits() {
450            let bytes = self.neg().to_be_bytes();
451            // wrapping_neg handles i128::MIN: bytes of 2^127 decode to i128::MIN.
452            // Because it fits in i128, we know the value is a valid i128 value
453            // so using wrapping_neg() cannot not silently miss an overflow.
454            i128::from_be_bytes(bytes[16..32].try_into().unwrap()).wrapping_neg()
455        } else {
456            let bytes = self.to_be_bytes();
457            i128::from_be_bytes(bytes[16..32].try_into().unwrap())
458        }
459    }
460
461    fn try_into_i128(self) -> Option<i128> {
462        self.fits_in_i128().then(|| self.to_i128())
463    }
464
465    fn try_to_u64(&self) -> Option<u64> {
466        (self.num_bits() <= 64).then(|| self.to_u128() as u64)
467    }
468
469    fn try_to_u32(&self) -> Option<u32> {
470        (self.num_bits() <= 32).then(|| self.to_u128() as u32)
471    }
472
473    /// Computes the inverse or returns zero if the inverse does not exist
474    /// Before using this FieldElement, please ensure that this behavior is necessary
475    fn inverse(&self) -> FieldElement<F> {
476        let inv = self.0.inverse().unwrap_or_else(F::zero);
477        FieldElement(inv)
478    }
479
480    fn to_hex(self) -> String {
481        let bytes = self.to_be_bytes();
482        hex::encode(bytes)
483    }
484
485    fn to_short_hex(self) -> String {
486        if self.is_zero() {
487            return "0x00".to_owned();
488        }
489
490        // Work directly with bytes
491        let bytes = self.to_be_bytes();
492
493        // Find the first non-zero byte
494        let first_nonzero = bytes.iter().position(|&b| b != 0).unwrap_or(bytes.len());
495        let trimmed = &bytes[first_nonzero..];
496
497        // Build the hex string directly
498        // Pre-allocate: "0x" + at least 2 chars per byte
499        let mut result = String::with_capacity(2 + trimmed.len() * 2);
500        result.push_str("0x");
501
502        // Format the first byte - use {:x} to avoid leading zero if byte >= 0x10
503        use std::fmt::Write;
504        write!(&mut result, "{:x}", trimmed[0]).unwrap();
505
506        // Ensure even length by padding if necessary
507        if !result.len().is_multiple_of(2) {
508            // Insert '0' after "0x" to make it even
509            result.insert(2, '0');
510        }
511
512        // Format remaining bytes with padding
513        for byte in &trimmed[1..] {
514            write!(&mut result, "{byte:02x}").unwrap();
515        }
516
517        result
518    }
519
520    fn from_hex(hex_str: &str) -> Option<FieldElement<F>> {
521        let value = hex_str.strip_prefix("0x").unwrap_or(hex_str);
522
523        // Decode directly, handling even length efficiently
524        let hex_as_bytes = if value.len().is_multiple_of(2) {
525            hex::decode(value).ok()?
526        } else {
527            // For odd length, prepend '0' to the string view only for decoding
528            let mut padded = String::with_capacity(value.len() + 1);
529            padded.push('0');
530            padded.push_str(value);
531            hex::decode(padded).ok()?
532        };
533
534        Some(FieldElement::from_be_bytes_reduce(&hex_as_bytes))
535    }
536
537    fn to_be_bytes(self) -> Vec<u8> {
538        let mut bytes = self.to_le_bytes();
539        bytes.reverse();
540        bytes
541    }
542
543    /// Converts the field element to a vector of bytes in little-endian order
544    fn to_le_bytes(self) -> Vec<u8> {
545        let mut bytes = Vec::new();
546        self.0.serialize_uncompressed(&mut bytes).unwrap();
547        bytes
548    }
549
550    /// Converts bytes into a FieldElement and applies a
551    /// reduction if needed.
552    fn from_be_bytes_reduce(bytes: &[u8]) -> FieldElement<F> {
553        FieldElement(F::from_be_bytes_mod_order(bytes))
554    }
555
556    /// Converts bytes in little-endian order into a FieldElement and applies a
557    /// reduction if needed.
558    fn from_le_bytes_reduce(bytes: &[u8]) -> FieldElement<F> {
559        FieldElement(F::from_le_bytes_mod_order(bytes))
560    }
561
562    /// Returns the closest number of bytes to the bits specified
563    /// This method truncates
564    fn fetch_nearest_bytes(&self, num_bits: usize) -> Vec<u8> {
565        fn nearest_bytes(num_bits: usize) -> usize {
566            num_bits.div_ceil(8) * 8
567        }
568
569        let num_bytes = nearest_bytes(num_bits);
570        let num_elements = num_bytes / 8;
571
572        let bytes = self.to_le_bytes();
573
574        bytes[0..num_elements].to_vec()
575    }
576}
577
578impl<F: PrimeField> Neg for FieldElement<F> {
579    type Output = FieldElement<F>;
580
581    fn neg(self) -> Self::Output {
582        FieldElement(-self.0)
583    }
584}
585
586impl<F: PrimeField> Mul for FieldElement<F> {
587    type Output = FieldElement<F>;
588    fn mul(mut self, rhs: FieldElement<F>) -> Self::Output {
589        self.0.mul_assign(&rhs.0);
590        FieldElement(self.0)
591    }
592}
593impl<F: PrimeField> Div for FieldElement<F> {
594    type Output = FieldElement<F>;
595    #[allow(clippy::suspicious_arithmetic_impl)]
596    fn div(self, rhs: FieldElement<F>) -> Self::Output {
597        self * rhs.inverse()
598    }
599}
600impl<F: PrimeField> Add for FieldElement<F> {
601    type Output = FieldElement<F>;
602    fn add(mut self, rhs: FieldElement<F>) -> Self::Output {
603        self.add_assign(rhs);
604        FieldElement(self.0)
605    }
606}
607impl<F: PrimeField> AddAssign for FieldElement<F> {
608    fn add_assign(&mut self, rhs: FieldElement<F>) {
609        self.0.add_assign(&rhs.0);
610    }
611}
612
613impl<F: PrimeField> Sub for FieldElement<F> {
614    type Output = FieldElement<F>;
615    fn sub(mut self, rhs: FieldElement<F>) -> Self::Output {
616        self.sub_assign(rhs);
617        FieldElement(self.0)
618    }
619}
620impl<F: PrimeField> SubAssign for FieldElement<F> {
621    fn sub_assign(&mut self, rhs: FieldElement<F>) {
622        self.0.sub_assign(&rhs.0);
623    }
624}
625
626impl<F: PrimeField> MsgpackTagged for FieldElement<F> {
627    const TAGGED: msgpack_tagged::Tagged = msgpack_tagged::Tagged::empty_product();
628
629    /// `F` is going to be a prime field from e.g. arkworks,
630    /// which is a primitive and doesn't implement `MsgpackTagged`,
631    /// so we have nothing to register.
632    fn register_into(_reg: &mut msgpack_tagged::TagRegistry) {}
633}
634
635#[cfg(test)]
636mod tests {
637    use super::{AcirField, FieldElement};
638    use proptest::prelude::*;
639    use std::ops::Neg;
640
641    #[test]
642    fn requires_zero_bit_to_hold_zero() {
643        let field = FieldElement::<ark_bn254::Fr>::zero();
644        assert_eq!(field.num_bits(), 0);
645    }
646
647    #[test]
648    fn requires_one_bit_to_hold_one() {
649        let field = FieldElement::<ark_bn254::Fr>::one();
650        assert_eq!(field.num_bits(), 1);
651    }
652
653    proptest! {
654        #[test]
655        fn num_bits_agrees_with_ilog2(num in 1u128..) {
656            let field = FieldElement::<ark_bn254::Fr>::from(num);
657            prop_assert_eq!(field.num_bits(), num.ilog2() + 1);
658        }
659    }
660
661    #[test]
662    fn test_fits_in_u128() {
663        let field = FieldElement::<ark_bn254::Fr>::from(u128::MAX);
664        assert_eq!(field.num_bits(), 128);
665        assert!(field.fits_in_u128());
666        let big_field = field + FieldElement::one();
667        assert_eq!(big_field.num_bits(), 129);
668        assert!(!big_field.fits_in_u128());
669    }
670
671    #[test]
672    fn test_to_u128_basic() {
673        type F = FieldElement<ark_bn254::Fr>;
674
675        // Test zero
676        assert_eq!(F::zero().to_u128(), 0);
677
678        // Test small values
679        assert_eq!(F::from(1_u128).to_u128(), 1);
680        assert_eq!(F::from(42_u128).to_u128(), 42);
681        assert_eq!(F::from(1000_u128).to_u128(), 1000);
682
683        // Test u128::MAX
684        assert_eq!(F::from(u128::MAX).to_u128(), u128::MAX);
685
686        // Test power of 2 boundaries
687        assert_eq!(F::from(1_u128 << 127).to_u128(), 1_u128 << 127);
688        assert_eq!(F::from((1_u128 << 127) - 1).to_u128(), (1_u128 << 127) - 1);
689    }
690
691    #[test]
692    #[should_panic(expected = "field element too large for u128")]
693    fn test_to_u128_panics_on_overflow() {
694        type F = FieldElement<ark_bn254::Fr>;
695
696        // Create a field element larger than u128::MAX
697        let too_large = F::from(u128::MAX) + F::one();
698        too_large.to_u128(); // Should panic
699    }
700
701    #[test]
702    fn test_try_into_u128() {
703        type F = FieldElement<ark_bn254::Fr>;
704
705        // Valid conversions
706        assert_eq!(F::zero().try_into_u128(), Some(0));
707        assert_eq!(F::from(42_u128).try_into_u128(), Some(42));
708        assert_eq!(F::from(u128::MAX).try_into_u128(), Some(u128::MAX));
709
710        // Invalid conversion
711        let too_large = F::from(u128::MAX) + F::one();
712        assert_eq!(too_large.try_into_u128(), None);
713    }
714
715    #[test]
716    fn test_fits_in_i128() {
717        type F = FieldElement<ark_bn254::Fr>;
718
719        // Positive values that fit
720        assert!(F::zero().fits_in_i128());
721        assert!(F::from(1_i128).fits_in_i128());
722        assert!(F::from(42_i128).fits_in_i128());
723        assert!(F::from(i128::MAX).fits_in_i128());
724
725        // Negative values that fit
726        assert!(F::from(-1_i128).fits_in_i128());
727        assert!(F::from(-42_i128).fits_in_i128());
728        assert!(F::from(i128::MIN + 1).fits_in_i128());
729        assert!(F::from(i128::MIN).fits_in_i128());
730
731        // Boundary: 2^127 - 1 fits (i128::MAX)
732        assert!(F::from((1_u128 << 127) - 1).fits_in_i128());
733
734        // Boundary: the positive field element 2^127 does NOT fit (exceeds i128::MAX).
735        // This is distinct from F::from(i128::MIN), which is the field element p - 2^127.
736        assert!(!F::from(1_u128 << 127).fits_in_i128());
737
738        // Values that don't fit
739        let too_large = F::from(u128::MAX);
740        assert!(!too_large.fits_in_i128());
741    }
742
743    #[test]
744    fn test_to_i128_positive() {
745        type F = FieldElement<ark_bn254::Fr>;
746
747        // Test positive values
748        assert_eq!(F::zero().to_i128(), 0);
749        assert_eq!(F::from(1_i128).to_i128(), 1);
750        assert_eq!(F::from(42_i128).to_i128(), 42);
751        assert_eq!(F::from(1000_i128).to_i128(), 1000);
752        assert_eq!(F::from(i128::MAX).to_i128(), i128::MAX);
753    }
754
755    #[test]
756    fn test_to_i128_negative() {
757        type F = FieldElement<ark_bn254::Fr>;
758
759        // Test negative values
760        assert_eq!(F::from(-1_i128).to_i128(), -1);
761        assert_eq!(F::from(-42_i128).to_i128(), -42);
762        assert_eq!(F::from(-1000_i128).to_i128(), -1000);
763
764        // Test boundary values
765        assert_eq!(F::from(-i128::MAX).to_i128(), -i128::MAX);
766        assert_eq!(F::from(i128::MIN + 1).to_i128(), i128::MIN + 1);
767        assert_eq!(F::from(i128::MIN).to_i128(), i128::MIN);
768    }
769
770    #[test]
771    fn test_to_i128_roundtrip() {
772        type F = FieldElement<ark_bn254::Fr>;
773
774        // Test roundtrip for various values
775        let test_values = vec![
776            0_i128,
777            1,
778            -1,
779            42,
780            -42,
781            i128::MAX,
782            i128::MAX - 1,
783            i128::MIN,
784            i128::MIN + 1,
785            -i128::MAX,
786        ];
787
788        for value in test_values {
789            let field = F::from(value);
790            assert!(field.fits_in_i128(), "Value {value} should fit in i128");
791            assert_eq!(field.to_i128(), value, "Roundtrip failed for {value}");
792        }
793    }
794
795    #[test]
796    #[should_panic(expected = "field element too large for i128")]
797    fn test_to_i128_panics_on_positive_overflow() {
798        type F = FieldElement<ark_bn254::Fr>;
799
800        // 2^127 is too large (exceeds i128::MAX)
801        let too_large = F::from(1_u128 << 127);
802        too_large.to_i128(); // Should panic
803    }
804
805    #[test]
806    #[should_panic(expected = "field element too large for i128")]
807    fn test_to_i128_panics_on_large_value() {
808        type F = FieldElement<ark_bn254::Fr>;
809
810        // Large positive value that doesn't fit
811        let too_large = F::from(u128::MAX);
812        too_large.to_i128(); // Should panic
813    }
814
815    #[test]
816    fn test_try_into_i128() {
817        type F = FieldElement<ark_bn254::Fr>;
818        // Valid positive conversions
819        assert_eq!(F::zero().try_into_i128(), Some(0));
820        assert_eq!(F::from(42_i128).try_into_i128(), Some(42));
821        assert_eq!(F::from(i128::MAX).try_into_i128(), Some(i128::MAX));
822        assert_eq!(F::from(-i128::MAX).try_into_i128(), Some(-i128::MAX));
823
824        // Valid negative conversions
825        assert_eq!(F::from(-1_i128).try_into_i128(), Some(-1));
826        assert_eq!(F::from(-42_i128).try_into_i128(), Some(-42));
827        assert_eq!(F::from(i128::MIN + 1).try_into_i128(), Some(i128::MIN + 1));
828        assert_eq!(F::from(i128::MAX - 1).try_into_i128(), Some(i128::MAX - 1));
829        assert_eq!(F::from(1_i128 << 126).try_into_i128(), Some(1_i128 << 126));
830        assert_eq!(F::from(-((1_i128 << 126) - 1)).try_into_i128(), Some(-((1_i128 << 126) - 1)));
831        // i128::MIN (= -2^127) fits: its field representation is p - 2^127, which is
832        // the same field element as F::from(1_u128 << 127).neg().
833        assert_eq!(F::from(i128::MIN).try_into_i128(), Some(i128::MIN));
834        assert_eq!(F::from(1_u128 << 127).neg().try_into_i128(), Some(i128::MIN));
835        // Invalid conversions
836        assert_eq!(F::from(1_u128 << 127).try_into_i128(), None);
837        assert_eq!(F::from(u128::MAX).try_into_i128(), None);
838        // A few other invalid values
839        assert_eq!(F::from((1_u128 << 127) + 1).try_into_i128(), None);
840        assert_eq!(F::from((1_u128 << 127) + 1000).try_into_i128(), None);
841        assert_eq!(F::from((1_u128 << 127) + 1).neg().try_into_i128(), None);
842        assert_eq!(F::from((1_u128 << 127) + 100).try_into_i128(), None);
843        assert_eq!(F::from((1_u128 << 127) + 100).neg().try_into_i128(), None);
844    }
845
846    #[test]
847    fn serialize_fixed_test_vectors() {
848        // Serialized field elements from of 0, -1, -2, -3
849        let hex_strings = vec![
850            "0000000000000000000000000000000000000000000000000000000000000000",
851            "30644e72e131a029b85045b68181585d2833e84879b9709143e1f593f0000000",
852            "30644e72e131a029b85045b68181585d2833e84879b9709143e1f593efffffff",
853            "30644e72e131a029b85045b68181585d2833e84879b9709143e1f593effffffe",
854        ];
855
856        for (i, string) in hex_strings.into_iter().enumerate() {
857            let minus_i_field_element = -FieldElement::<ark_bn254::Fr>::from(i as i128);
858            assert_eq!(minus_i_field_element.to_hex(), string);
859        }
860    }
861
862    #[test]
863    fn max_num_bits_smoke() {
864        let max_num_bits_bn254 = FieldElement::<ark_bn254::Fr>::max_num_bits();
865        assert_eq!(max_num_bits_bn254, 254);
866    }
867
868    proptest! {
869        #[test]
870        fn test_endianness_prop(value in any::<u64>()) {
871            let field = FieldElement::<ark_bn254::Fr>::from(value);
872            // Test serialization consistency
873            let le_bytes = field.to_le_bytes();
874            let be_bytes = field.to_be_bytes();
875
876            let mut reversed_le = le_bytes.clone();
877            reversed_le.reverse();
878            prop_assert_eq!(&be_bytes, &reversed_le, "BE bytes should be reverse of LE bytes");
879
880            // Test deserialization consistency
881            let from_le = FieldElement::from_le_bytes_reduce(&le_bytes);
882            let from_be = FieldElement::from_be_bytes_reduce(&be_bytes);
883            prop_assert_eq!(from_le, from_be, "Deserialization should be consistent between LE and BE");
884            prop_assert_eq!(from_le, field, "Deserialized value should match original");
885        }
886    }
887
888    #[test]
889    fn test_endianness() {
890        let field = FieldElement::<ark_bn254::Fr>::from(0x1234_5678_u32);
891        let le_bytes = field.to_le_bytes();
892        let be_bytes = field.to_be_bytes();
893
894        // Check that the bytes are reversed between BE and LE
895        let mut reversed_le = le_bytes.clone();
896        reversed_le.reverse();
897        assert_eq!(&be_bytes, &reversed_le);
898
899        // Verify we can reconstruct the same field element from either byte order
900        let from_le = FieldElement::from_le_bytes_reduce(&le_bytes);
901        let from_be = FieldElement::from_be_bytes_reduce(&be_bytes);
902        assert_eq!(from_le, from_be);
903        assert_eq!(from_le, field);
904
905        // Additional test with a larger number to ensure proper byte handling
906        let large_field = FieldElement::<ark_bn254::Fr>::from(0x0123_4567_89AB_CDEF_u64); // cSpell:disable-line
907        let large_le = large_field.to_le_bytes();
908        let reconstructed = FieldElement::from_le_bytes_reduce(&large_le);
909        assert_eq!(reconstructed, large_field);
910    }
911
912    proptest! {
913        // This currently panics due to the fact that we allow inputs which are greater than the field modulus,
914        // automatically reducing them to fit within the canonical range.
915        #[test]
916        #[should_panic(expected = "serialized field element is not equal to input")]
917        fn recovers_original_hex_string(hex in "[0-9a-f]{64}") {
918            let fe: FieldElement::<ark_bn254::Fr> = FieldElement::from_hex(&hex).expect("should accept any 32 byte hex string");
919            let output_hex = fe.to_hex();
920
921            prop_assert_eq!(hex, output_hex, "serialized field element is not equal to input");
922        }
923
924        #[test]
925        fn accepts_odd_length_hex_strings(hex in "(?:0x)[0-9a-fA-F]+") {
926            // Here we inject a "0" immediately after the "0x" (if it exists) to construct an equivalent
927            // hex string with the opposite parity length.
928            let insert_index = if hex.starts_with("0x") { 2 } else { 0 };
929            let mut opposite_parity_string = hex.clone();
930            opposite_parity_string.insert(insert_index, '0');
931
932            let fe_1: FieldElement::<ark_bn254::Fr> = FieldElement::from_hex(&hex).unwrap();
933            let fe_2: FieldElement::<ark_bn254::Fr> = FieldElement::from_hex(&opposite_parity_string).unwrap();
934
935            prop_assert_eq!(fe_1, fe_2, "equivalent hex strings with opposite parity deserialized to different values");
936        }
937    }
938
939    #[test]
940    fn test_to_hex() {
941        type F = FieldElement<ark_bn254::Fr>;
942        assert_eq!(
943            F::zero().to_hex(),
944            "0000000000000000000000000000000000000000000000000000000000000000"
945        );
946        assert_eq!(
947            F::one().to_hex(),
948            "0000000000000000000000000000000000000000000000000000000000000001"
949        );
950        assert_eq!(
951            F::from(0x123_u128).to_hex(),
952            "0000000000000000000000000000000000000000000000000000000000000123"
953        );
954        assert_eq!(
955            F::from(0x1234_u128).to_hex(),
956            "0000000000000000000000000000000000000000000000000000000000001234"
957        );
958    }
959
960    #[test]
961    fn test_to_short_hex() {
962        type F = FieldElement<ark_bn254::Fr>;
963        assert_eq!(F::zero().to_short_hex(), "0x00");
964        assert_eq!(F::one().to_short_hex(), "0x01");
965        assert_eq!(F::from(0x123_u128).to_short_hex(), "0x0123");
966        assert_eq!(F::from(0x1234_u128).to_short_hex(), "0x1234");
967    }
968
969    #[test]
970    fn to_string_as_signed_integer() {
971        type F = FieldElement<ark_bn254::Fr>;
972        assert_eq!(F::zero().to_string_as_signed_integer(8), "0");
973        assert_eq!(F::one().to_string_as_signed_integer(8), "1");
974        assert_eq!(F::from(127_u128).to_string_as_signed_integer(8), "127");
975        assert_eq!(F::from(128_u128).to_string_as_signed_integer(8), "-128");
976        assert_eq!(F::from(129_u128).to_string_as_signed_integer(8), "-127");
977        assert_eq!(F::from(255_u128).to_string_as_signed_integer(8), "-1");
978        assert_eq!(F::from(32767_u128).to_string_as_signed_integer(16), "32767");
979        assert_eq!(F::from(32768_u128).to_string_as_signed_integer(16), "-32768");
980        assert_eq!(F::from(65535_u128).to_string_as_signed_integer(16), "-1");
981    }
982}
acir_field/field_element.rs

acir_field/
field_element.rs
