acir_field/
field_element.rs

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

acir_field/
field_element.rs
