acir_field/
field_element.rs

1use ark_ff::PrimeField;
2use ark_ff::Zero;
3use ark_std::io::Write;
4use num_bigint::BigUint;
5use serde::{Deserialize, Serialize};
6use std::borrow::Cow;
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<T: PrimeField> Serialize for FieldElement<T> {
66    fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>
67    where
68        S: serde::Serializer,
69    {
70        self.to_be_bytes().serialize(serializer)
71    }
72}
73
74impl<'de, T: PrimeField> Deserialize<'de> for FieldElement<T> {
75    fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>
76    where
77        D: serde::Deserializer<'de>,
78    {
79        let s: Cow<'de, [u8]> = Deserialize::deserialize(deserializer)?;
80        Ok(Self::from_be_bytes_reduce(&s))
81    }
82}
83
84impl<F: PrimeField> From<u128> for FieldElement<F> {
85    fn from(a: u128) -> FieldElement<F> {
86        FieldElement(F::from(a))
87    }
88}
89
90impl<F: PrimeField> From<usize> for FieldElement<F> {
91    fn from(a: usize) -> FieldElement<F> {
92        FieldElement::from(a as u64)
93    }
94}
95
96impl<F: PrimeField> From<u64> for FieldElement<F> {
97    fn from(a: u64) -> FieldElement<F> {
98        FieldElement(F::from(a))
99    }
100}
101
102impl<F: PrimeField> From<u32> for FieldElement<F> {
103    fn from(a: u32) -> FieldElement<F> {
104        FieldElement(F::from(a))
105    }
106}
107
108impl<F: PrimeField> From<bool> for FieldElement<F> {
109    fn from(boolean: bool) -> FieldElement<F> {
110        if boolean { FieldElement::one() } else { FieldElement::zero() }
111    }
112}
113
114impl<F: PrimeField> FieldElement<F> {
115    /// Constructs a `FieldElement` from the underlying prime field representation.
116    ///
117    /// This wraps an `ark_ff::PrimeField` element into a `FieldElement`.
118    pub fn from_repr(field: F) -> Self {
119        Self(field)
120    }
121
122    /// Extracts the underlying prime field representation.
123    ///
124    /// This returns the wrapped `ark_ff::PrimeField` element.
125    pub fn into_repr(self) -> F {
126        self.0
127    }
128
129    /// Returns true if this field element can be represented as a u128.
130    ///
131    /// A field element fits in u128 if it requires at most 128 bits to represent,
132    /// i.e., if its value is in the range [0, 2^128 - 1].
133    pub fn fits_in_u128(&self) -> bool {
134        self.num_bits() <= 128
135    }
136
137    /// Returns true if this field element can be represented as an i128.
138    ///
139    /// An i128 can represent values in the range [i128::MIN, i128::MAX], which corresponds
140    /// to field elements in [0, 2^127 - 1] (positive) and [p - 2^127, p - 1] (negative),
141    /// where p is the field modulus. Note that 2^127 itself cannot be represented as i128
142    /// since it is not in the negative range.
143    pub fn fits_in_i128(&self) -> bool {
144        let num_bits = u32::min(self.neg().num_bits(), self.num_bits());
145        num_bits <= 127 && self != &FieldElement::from(I128_SIGN_BOUNDARY)
146    }
147
148    /// Returns None, if the string is not a canonical
149    /// representation of a field element; less than the order
150    /// or if the hex string is invalid.
151    /// This method can be used for both hex and decimal representations.
152    pub fn try_from_str(input: &str) -> Option<FieldElement<F>> {
153        if input.contains('x') {
154            return FieldElement::from_hex(input);
155        }
156
157        let fr = F::from_str(input).ok()?;
158        Some(FieldElement(fr))
159    }
160
161    /// Assume this field element holds a signed integer of the given `bit_size` and format
162    /// it as a string. The range of valid values for this field element is `0..2^bit_size`
163    /// with `0..2^(bit_size - 1)` representing positive values and `2^(bit_size - 1)..2^bit_size`
164    /// representing negative values (as is commonly done for signed integers).
165    /// `2^(bit_size - 1)` is the lowest negative value, so for example if bit_size is 8 then
166    /// `0..127` map to `0..127`, `128` maps to `-128`, `129` maps to `-127` and `255` maps to `-1`.
167    /// If `self` falls outside of the valid range it's formatted as-is.
168    pub fn to_string_as_signed_integer(self, bit_size: u32) -> String {
169        assert!(bit_size <= 128);
170        if self.num_bits() > bit_size {
171            return self.to_string();
172        }
173
174        // Compute the maximum value that is considered a positive value
175        let max = if bit_size == 128 { i128::MAX as u128 } else { (1 << (bit_size - 1)) - 1 };
176        if self.to_u128() > max {
177            let f = FieldElement::from(2u32).pow(&bit_size.into()) - self;
178            format!("-{f}")
179        } else {
180            self.to_string()
181        }
182    }
183}
184
185impl<F: PrimeField> AcirField for FieldElement<F> {
186    fn one() -> FieldElement<F> {
187        FieldElement(F::one())
188    }
189    fn zero() -> FieldElement<F> {
190        FieldElement(F::zero())
191    }
192
193    fn is_zero(&self) -> bool {
194        self == &Self::zero()
195    }
196    fn is_one(&self) -> bool {
197        self == &Self::one()
198    }
199
200    fn pow(&self, exponent: &Self) -> Self {
201        FieldElement(self.0.pow(exponent.0.into_bigint()))
202    }
203
204    /// Maximum number of bits needed to represent a field element
205    /// This is not the amount of bits being used to represent a field element
206    /// Example, you only need 254 bits to represent a field element in BN256
207    /// But the representation uses 256 bits, so the top two bits are always zero
208    /// This method would return 254
209    fn max_num_bits() -> u32 {
210        F::MODULUS_BIT_SIZE
211    }
212
213    /// Maximum numbers of bytes needed to represent a field element
214    /// We are not guaranteed that the number of bits being used to represent a field element
215    /// will always be divisible by 8. If the case that it is not, we add one to the max number of bytes
216    /// For example, a max bit size of 254 would give a max byte size of 32.
217    fn max_num_bytes() -> u32 {
218        let num_bytes = Self::max_num_bits() / 8;
219        if Self::max_num_bits() % 8 == 0 { num_bytes } else { num_bytes + 1 }
220    }
221
222    fn modulus() -> BigUint {
223        F::MODULUS.into()
224    }
225
226    /// This is the number of bits required to represent this specific field element
227    fn num_bits(&self) -> u32 {
228        let mut bit_counter = BitCounter::default();
229        self.0.serialize_uncompressed(&mut bit_counter).unwrap();
230        bit_counter.bits()
231    }
232
233    fn to_u128(self) -> u128 {
234        if !self.fits_in_u128() {
235            panic!("field element too large for u128");
236        }
237        let as_bigint = self.0.into_bigint();
238        let limbs = as_bigint.as_ref();
239
240        let mut result = u128::from(limbs[0]);
241        if limbs.len() > 1 {
242            let high_limb = u128::from(limbs[1]);
243            result += high_limb << 64;
244        }
245
246        result
247    }
248
249    fn try_into_u128(self) -> Option<u128> {
250        self.fits_in_u128().then(|| self.to_u128())
251    }
252
253    fn to_i128(self) -> i128 {
254        if !self.fits_in_i128() {
255            panic!("field element too large for i128");
256        }
257        // Negative integers are represented by the range [p + i128::MIN, p) while
258        // positive integers are represented by the range [0, i128::MAX).
259        // We can then differentiate positive from negative values by their MSB.
260        if self.neg().num_bits() < self.num_bits() {
261            let bytes = self.neg().to_be_bytes();
262            i128::from_be_bytes(bytes[16..32].try_into().unwrap()).neg()
263        } else {
264            let bytes = self.to_be_bytes();
265            i128::from_be_bytes(bytes[16..32].try_into().unwrap())
266        }
267    }
268
269    fn try_into_i128(self) -> Option<i128> {
270        self.fits_in_i128().then(|| self.to_i128())
271    }
272
273    fn try_to_u64(&self) -> Option<u64> {
274        (self.num_bits() <= 64).then(|| self.to_u128() as u64)
275    }
276
277    fn try_to_u32(&self) -> Option<u32> {
278        (self.num_bits() <= 32).then(|| self.to_u128() as u32)
279    }
280
281    /// Computes the inverse or returns zero if the inverse does not exist
282    /// Before using this FieldElement, please ensure that this behavior is necessary
283    fn inverse(&self) -> FieldElement<F> {
284        let inv = self.0.inverse().unwrap_or_else(F::zero);
285        FieldElement(inv)
286    }
287
288    fn to_hex(self) -> String {
289        let bytes = self.to_be_bytes();
290        hex::encode(bytes)
291    }
292
293    fn to_short_hex(self) -> String {
294        if self.is_zero() {
295            return "0x00".to_owned();
296        }
297
298        // Work directly with bytes
299        let bytes = self.to_be_bytes();
300
301        // Find the first non-zero byte
302        let first_nonzero = bytes.iter().position(|&b| b != 0).unwrap_or(bytes.len());
303        let trimmed = &bytes[first_nonzero..];
304
305        // Build the hex string directly
306        // Pre-allocate: "0x" + at least 2 chars per byte
307        let mut result = String::with_capacity(2 + trimmed.len() * 2);
308        result.push_str("0x");
309
310        // Format the first byte - use {:x} to avoid leading zero if byte >= 0x10
311        use std::fmt::Write;
312        write!(&mut result, "{:x}", trimmed[0]).unwrap();
313
314        // Ensure even length by padding if necessary
315        if !result.len().is_multiple_of(2) {
316            // Insert '0' after "0x" to make it even
317            result.insert(2, '0');
318        }
319
320        // Format remaining bytes with padding
321        for byte in &trimmed[1..] {
322            write!(&mut result, "{byte:02x}").unwrap();
323        }
324
325        result
326    }
327
328    fn from_hex(hex_str: &str) -> Option<FieldElement<F>> {
329        let value = hex_str.strip_prefix("0x").unwrap_or(hex_str);
330
331        // Decode directly, handling even length efficiently
332        let hex_as_bytes = if value.len().is_multiple_of(2) {
333            hex::decode(value).ok()?
334        } else {
335            // For odd length, prepend '0' to the string view only for decoding
336            let mut padded = String::with_capacity(value.len() + 1);
337            padded.push('0');
338            padded.push_str(value);
339            hex::decode(padded).ok()?
340        };
341
342        Some(FieldElement::from_be_bytes_reduce(&hex_as_bytes))
343    }
344
345    fn to_be_bytes(self) -> Vec<u8> {
346        let mut bytes = self.to_le_bytes();
347        bytes.reverse();
348        bytes
349    }
350
351    /// Converts the field element to a vector of bytes in little-endian order
352    fn to_le_bytes(self) -> Vec<u8> {
353        let mut bytes = Vec::new();
354        self.0.serialize_uncompressed(&mut bytes).unwrap();
355        bytes
356    }
357
358    /// Converts bytes into a FieldElement and applies a
359    /// reduction if needed.
360    fn from_be_bytes_reduce(bytes: &[u8]) -> FieldElement<F> {
361        FieldElement(F::from_be_bytes_mod_order(bytes))
362    }
363
364    /// Converts bytes in little-endian order into a FieldElement and applies a
365    /// reduction if needed.
366    fn from_le_bytes_reduce(bytes: &[u8]) -> FieldElement<F> {
367        FieldElement(F::from_le_bytes_mod_order(bytes))
368    }
369
370    /// Returns the closest number of bytes to the bits specified
371    /// This method truncates
372    fn fetch_nearest_bytes(&self, num_bits: usize) -> Vec<u8> {
373        fn nearest_bytes(num_bits: usize) -> usize {
374            num_bits.div_ceil(8) * 8
375        }
376
377        let num_bytes = nearest_bytes(num_bits);
378        let num_elements = num_bytes / 8;
379
380        let bytes = self.to_le_bytes();
381
382        bytes[0..num_elements].to_vec()
383    }
384}
385
386impl<F: PrimeField> Neg for FieldElement<F> {
387    type Output = FieldElement<F>;
388
389    fn neg(self) -> Self::Output {
390        FieldElement(-self.0)
391    }
392}
393
394impl<F: PrimeField> Mul for FieldElement<F> {
395    type Output = FieldElement<F>;
396    fn mul(mut self, rhs: FieldElement<F>) -> Self::Output {
397        self.0.mul_assign(&rhs.0);
398        FieldElement(self.0)
399    }
400}
401impl<F: PrimeField> Div for FieldElement<F> {
402    type Output = FieldElement<F>;
403    #[allow(clippy::suspicious_arithmetic_impl)]
404    fn div(self, rhs: FieldElement<F>) -> Self::Output {
405        self * rhs.inverse()
406    }
407}
408impl<F: PrimeField> Add for FieldElement<F> {
409    type Output = FieldElement<F>;
410    fn add(mut self, rhs: FieldElement<F>) -> Self::Output {
411        self.add_assign(rhs);
412        FieldElement(self.0)
413    }
414}
415impl<F: PrimeField> AddAssign for FieldElement<F> {
416    fn add_assign(&mut self, rhs: FieldElement<F>) {
417        self.0.add_assign(&rhs.0);
418    }
419}
420
421impl<F: PrimeField> Sub for FieldElement<F> {
422    type Output = FieldElement<F>;
423    fn sub(mut self, rhs: FieldElement<F>) -> Self::Output {
424        self.sub_assign(rhs);
425        FieldElement(self.0)
426    }
427}
428impl<F: PrimeField> SubAssign for FieldElement<F> {
429    fn sub_assign(&mut self, rhs: FieldElement<F>) {
430        self.0.sub_assign(&rhs.0);
431    }
432}
433
434#[derive(Default, Debug)]
435struct BitCounter {
436    /// Total number of non-zero bytes we found.
437    count: usize,
438    /// Total bytes we found.
439    total: usize,
440    /// The last non-zero byte we found.
441    head_byte: u8,
442}
443
444impl BitCounter {
445    fn bits(&self) -> u32 {
446        // If we don't have a non-zero byte then the field element is zero,
447        // which we consider to require a zero bits to represent.
448        if self.count == 0 {
449            return 0;
450        }
451
452        let num_bits_for_head_byte = self.head_byte.ilog2();
453
454        // Each remaining byte in the byte decomposition requires 8 bits.
455        //
456        // Note: count will panic if it goes over usize::MAX.
457        // This may not be suitable for devices whose usize < u16
458        let tail_length = (self.count - 1) as u32;
459        8 * tail_length + num_bits_for_head_byte + 1
460    }
461}
462
463impl Write for BitCounter {
464    fn write(&mut self, buf: &[u8]) -> ark_std::io::Result<usize> {
465        for byte in buf {
466            self.total += 1;
467            if *byte != 0 {
468                self.count = self.total;
469                self.head_byte = *byte;
470            }
471        }
472        Ok(buf.len())
473    }
474
475    fn flush(&mut self) -> ark_std::io::Result<()> {
476        Ok(())
477    }
478}
479
480#[cfg(test)]
481mod tests {
482    use super::{AcirField, FieldElement};
483    use proptest::prelude::*;
484    use std::ops::Neg;
485
486    #[test]
487    fn requires_zero_bit_to_hold_zero() {
488        let field = FieldElement::<ark_bn254::Fr>::zero();
489        assert_eq!(field.num_bits(), 0);
490    }
491
492    #[test]
493    fn requires_one_bit_to_hold_one() {
494        let field = FieldElement::<ark_bn254::Fr>::one();
495        assert_eq!(field.num_bits(), 1);
496    }
497
498    proptest! {
499        #[test]
500        fn num_bits_agrees_with_ilog2(num in 1u128..) {
501            let field = FieldElement::<ark_bn254::Fr>::from(num);
502            prop_assert_eq!(field.num_bits(), num.ilog2() + 1);
503        }
504    }
505
506    #[test]
507    fn test_fits_in_u128() {
508        let field = FieldElement::<ark_bn254::Fr>::from(u128::MAX);
509        assert_eq!(field.num_bits(), 128);
510        assert!(field.fits_in_u128());
511        let big_field = field + FieldElement::one();
512        assert_eq!(big_field.num_bits(), 129);
513        assert!(!big_field.fits_in_u128());
514    }
515
516    #[test]
517    fn test_to_u128_basic() {
518        type F = FieldElement<ark_bn254::Fr>;
519
520        // Test zero
521        assert_eq!(F::zero().to_u128(), 0);
522
523        // Test small values
524        assert_eq!(F::from(1_u128).to_u128(), 1);
525        assert_eq!(F::from(42_u128).to_u128(), 42);
526        assert_eq!(F::from(1000_u128).to_u128(), 1000);
527
528        // Test u128::MAX
529        assert_eq!(F::from(u128::MAX).to_u128(), u128::MAX);
530
531        // Test power of 2 boundaries
532        assert_eq!(F::from(1_u128 << 127).to_u128(), 1_u128 << 127);
533        assert_eq!(F::from((1_u128 << 127) - 1).to_u128(), (1_u128 << 127) - 1);
534    }
535
536    #[test]
537    #[should_panic(expected = "field element too large for u128")]
538    fn test_to_u128_panics_on_overflow() {
539        type F = FieldElement<ark_bn254::Fr>;
540
541        // Create a field element larger than u128::MAX
542        let too_large = F::from(u128::MAX) + F::one();
543        too_large.to_u128(); // Should panic
544    }
545
546    #[test]
547    fn test_try_into_u128() {
548        type F = FieldElement<ark_bn254::Fr>;
549
550        // Valid conversions
551        assert_eq!(F::zero().try_into_u128(), Some(0));
552        assert_eq!(F::from(42_u128).try_into_u128(), Some(42));
553        assert_eq!(F::from(u128::MAX).try_into_u128(), Some(u128::MAX));
554
555        // Invalid conversion
556        let too_large = F::from(u128::MAX) + F::one();
557        assert_eq!(too_large.try_into_u128(), None);
558    }
559
560    #[test]
561    fn test_fits_in_i128() {
562        type F = FieldElement<ark_bn254::Fr>;
563
564        // Positive values that fit
565        assert!(F::zero().fits_in_i128());
566        assert!(F::from(1_i128).fits_in_i128());
567        assert!(F::from(42_i128).fits_in_i128());
568        assert!(F::from(i128::MAX).fits_in_i128());
569
570        // Negative values that fit (except i128::MIN)
571        assert!(F::from(-1_i128).fits_in_i128());
572        assert!(F::from(-42_i128).fits_in_i128());
573        assert!(F::from(i128::MIN + 1).fits_in_i128());
574
575        // Boundary: 2^127 - 1 fits (i128::MAX)
576        assert!(F::from((1_u128 << 127) - 1).fits_in_i128());
577
578        // Boundary: 2^127 does NOT fit (exceeds i128::MAX, not negative)
579        // Note: This also means i128::MIN doesn't fit, as it converts to a field element
580        // that when interpreted as unsigned equals 2^127
581        assert!(!F::from(1_u128 << 127).fits_in_i128());
582        assert!(!F::from(i128::MIN).fits_in_i128());
583
584        // Values that don't fit
585        let too_large = F::from(u128::MAX);
586        assert!(!too_large.fits_in_i128());
587    }
588
589    #[test]
590    fn test_to_i128_positive() {
591        type F = FieldElement<ark_bn254::Fr>;
592
593        // Test positive values
594        assert_eq!(F::zero().to_i128(), 0);
595        assert_eq!(F::from(1_i128).to_i128(), 1);
596        assert_eq!(F::from(42_i128).to_i128(), 42);
597        assert_eq!(F::from(1000_i128).to_i128(), 1000);
598        assert_eq!(F::from(i128::MAX).to_i128(), i128::MAX);
599    }
600
601    #[test]
602    fn test_to_i128_negative() {
603        type F = FieldElement<ark_bn254::Fr>;
604
605        // Test negative values
606        assert_eq!(F::from(-1_i128).to_i128(), -1);
607        assert_eq!(F::from(-42_i128).to_i128(), -42);
608        assert_eq!(F::from(-1000_i128).to_i128(), -1000);
609
610        // Test boundary values
611        assert_eq!(F::from(-i128::MAX).to_i128(), -i128::MAX);
612        assert_eq!(F::from(i128::MIN + 1).to_i128(), i128::MIN + 1);
613
614        // i128::MIN doesn't fit
615    }
616
617    #[test]
618    fn test_to_i128_roundtrip() {
619        type F = FieldElement<ark_bn254::Fr>;
620
621        // Test roundtrip for various values
622        // i128::MIN doesn't fit
623        let test_values =
624            vec![0_i128, 1, -1, 42, -42, i128::MAX, i128::MAX - 1, i128::MIN + 1, -i128::MAX];
625
626        for value in test_values {
627            let field = F::from(value);
628            assert!(field.fits_in_i128(), "Value {value} should fit in i128");
629            assert_eq!(field.to_i128(), value, "Roundtrip failed for {value}");
630        }
631    }
632
633    #[test]
634    #[should_panic(expected = "field element too large for i128")]
635    fn test_to_i128_panics_on_positive_overflow() {
636        type F = FieldElement<ark_bn254::Fr>;
637
638        // 2^127 is too large (exceeds i128::MAX)
639        let too_large = F::from(1_u128 << 127);
640        too_large.to_i128(); // Should panic
641    }
642
643    #[test]
644    #[should_panic(expected = "field element too large for i128")]
645    fn test_to_i128_panics_on_large_value() {
646        type F = FieldElement<ark_bn254::Fr>;
647
648        // Large positive value that doesn't fit
649        let too_large = F::from(u128::MAX);
650        too_large.to_i128(); // Should panic
651    }
652
653    #[test]
654    fn test_try_into_i128() {
655        type F = FieldElement<ark_bn254::Fr>;
656
657        // Valid positive conversions
658        assert_eq!(F::zero().try_into_i128(), Some(0));
659        assert_eq!(F::from(42_i128).try_into_i128(), Some(42));
660        assert_eq!(F::from(i128::MAX).try_into_i128(), Some(i128::MAX));
661        assert_eq!(F::from(-i128::MAX).try_into_i128(), Some(-i128::MAX));
662
663        // Valid negative conversions
664        assert_eq!(F::from(-1_i128).try_into_i128(), Some(-1));
665        assert_eq!(F::from(-42_i128).try_into_i128(), Some(-42));
666        assert_eq!(F::from(i128::MIN + 1).try_into_i128(), Some(i128::MIN + 1));
667        assert_eq!(F::from(i128::MAX - 1).try_into_i128(), Some(i128::MAX - 1));
668        assert_eq!(F::from(1_i128 << 126).try_into_i128(), Some(1_i128 << 126));
669        assert_eq!(F::from(-((1_i128 << 126) - 1)).try_into_i128(), Some(-((1_i128 << 126) - 1)));
670        // Invalid conversions
671        assert_eq!(F::from(1_u128 << 127).try_into_i128(), None);
672        assert_eq!(F::from(u128::MAX).try_into_i128(), None);
673        // i128::MIN doesn't fit due to implementation
674        assert_eq!(F::from(i128::MIN).try_into_i128(), None);
675        // A few other invalid values
676        assert_eq!(F::from((1_u128 << 127) + 1).try_into_i128(), None);
677        assert_eq!(F::from((1_u128 << 127) + 1000).try_into_i128(), None);
678        assert_eq!(F::from(1_u128 << 127).neg().try_into_i128(), None);
679        assert_eq!(F::from((1_u128 << 127) + 1).neg().try_into_i128(), None);
680        assert_eq!(F::from((1_u128 << 127) + 100).try_into_i128(), None);
681        assert_eq!(F::from((1_u128 << 127) + 100).neg().try_into_i128(), None);
682    }
683
684    #[test]
685    fn serialize_fixed_test_vectors() {
686        // Serialized field elements from of 0, -1, -2, -3
687        let hex_strings = vec![
688            "0000000000000000000000000000000000000000000000000000000000000000",
689            "30644e72e131a029b85045b68181585d2833e84879b9709143e1f593f0000000",
690            "30644e72e131a029b85045b68181585d2833e84879b9709143e1f593efffffff",
691            "30644e72e131a029b85045b68181585d2833e84879b9709143e1f593effffffe",
692        ];
693
694        for (i, string) in hex_strings.into_iter().enumerate() {
695            let minus_i_field_element = -FieldElement::<ark_bn254::Fr>::from(i as i128);
696            assert_eq!(minus_i_field_element.to_hex(), string);
697        }
698    }
699
700    #[test]
701    fn max_num_bits_smoke() {
702        let max_num_bits_bn254 = FieldElement::<ark_bn254::Fr>::max_num_bits();
703        assert_eq!(max_num_bits_bn254, 254);
704    }
705
706    proptest! {
707        #[test]
708        fn test_endianness_prop(value in any::<u64>()) {
709            let field = FieldElement::<ark_bn254::Fr>::from(value);
710            // Test serialization consistency
711            let le_bytes = field.to_le_bytes();
712            let be_bytes = field.to_be_bytes();
713
714            let mut reversed_le = le_bytes.clone();
715            reversed_le.reverse();
716            prop_assert_eq!(&be_bytes, &reversed_le, "BE bytes should be reverse of LE bytes");
717
718            // Test deserialization consistency
719            let from_le = FieldElement::from_le_bytes_reduce(&le_bytes);
720            let from_be = FieldElement::from_be_bytes_reduce(&be_bytes);
721            prop_assert_eq!(from_le, from_be, "Deserialization should be consistent between LE and BE");
722            prop_assert_eq!(from_le, field, "Deserialized value should match original");
723        }
724    }
725
726    #[test]
727    fn test_endianness() {
728        let field = FieldElement::<ark_bn254::Fr>::from(0x1234_5678_u32);
729        let le_bytes = field.to_le_bytes();
730        let be_bytes = field.to_be_bytes();
731
732        // Check that the bytes are reversed between BE and LE
733        let mut reversed_le = le_bytes.clone();
734        reversed_le.reverse();
735        assert_eq!(&be_bytes, &reversed_le);
736
737        // Verify we can reconstruct the same field element from either byte order
738        let from_le = FieldElement::from_le_bytes_reduce(&le_bytes);
739        let from_be = FieldElement::from_be_bytes_reduce(&be_bytes);
740        assert_eq!(from_le, from_be);
741        assert_eq!(from_le, field);
742
743        // Additional test with a larger number to ensure proper byte handling
744        let large_field = FieldElement::<ark_bn254::Fr>::from(0x0123_4567_89AB_CDEF_u64); // cSpell:disable-line
745        let large_le = large_field.to_le_bytes();
746        let reconstructed = FieldElement::from_le_bytes_reduce(&large_le);
747        assert_eq!(reconstructed, large_field);
748    }
749
750    proptest! {
751        // This currently panics due to the fact that we allow inputs which are greater than the field modulus,
752        // automatically reducing them to fit within the canonical range.
753        #[test]
754        #[should_panic(expected = "serialized field element is not equal to input")]
755        fn recovers_original_hex_string(hex in "[0-9a-f]{64}") {
756            let fe: FieldElement::<ark_bn254::Fr> = FieldElement::from_hex(&hex).expect("should accept any 32 byte hex string");
757            let output_hex = fe.to_hex();
758
759            prop_assert_eq!(hex, output_hex, "serialized field element is not equal to input");
760        }
761
762        #[test]
763        fn accepts_odd_length_hex_strings(hex in "(?:0x)[0-9a-fA-F]+") {
764            // Here we inject a "0" immediately after the "0x" (if it exists) to construct an equivalent
765            // hex string with the opposite parity length.
766            let insert_index = if hex.starts_with("0x") { 2 } else { 0 };
767            let mut opposite_parity_string = hex.to_string();
768            opposite_parity_string.insert(insert_index, '0');
769
770            let fe_1: FieldElement::<ark_bn254::Fr> = FieldElement::from_hex(&hex).unwrap();
771            let fe_2: FieldElement::<ark_bn254::Fr> = FieldElement::from_hex(&opposite_parity_string).unwrap();
772
773            prop_assert_eq!(fe_1, fe_2, "equivalent hex strings with opposite parity deserialized to different values");
774        }
775    }
776
777    #[test]
778    fn test_to_hex() {
779        type F = FieldElement<ark_bn254::Fr>;
780        assert_eq!(
781            F::zero().to_hex(),
782            "0000000000000000000000000000000000000000000000000000000000000000"
783        );
784        assert_eq!(
785            F::one().to_hex(),
786            "0000000000000000000000000000000000000000000000000000000000000001"
787        );
788        assert_eq!(
789            F::from(0x123_u128).to_hex(),
790            "0000000000000000000000000000000000000000000000000000000000000123"
791        );
792        assert_eq!(
793            F::from(0x1234_u128).to_hex(),
794            "0000000000000000000000000000000000000000000000000000000000001234"
795        );
796    }
797
798    #[test]
799    fn test_to_short_hex() {
800        type F = FieldElement<ark_bn254::Fr>;
801        assert_eq!(F::zero().to_short_hex(), "0x00");
802        assert_eq!(F::one().to_short_hex(), "0x01");
803        assert_eq!(F::from(0x123_u128).to_short_hex(), "0x0123");
804        assert_eq!(F::from(0x1234_u128).to_short_hex(), "0x1234");
805    }
806
807    #[test]
808    fn to_string_as_signed_integer() {
809        type F = FieldElement<ark_bn254::Fr>;
810        assert_eq!(F::zero().to_string_as_signed_integer(8), "0");
811        assert_eq!(F::one().to_string_as_signed_integer(8), "1");
812        assert_eq!(F::from(127_u128).to_string_as_signed_integer(8), "127");
813        assert_eq!(F::from(128_u128).to_string_as_signed_integer(8), "-128");
814        assert_eq!(F::from(129_u128).to_string_as_signed_integer(8), "-127");
815        assert_eq!(F::from(255_u128).to_string_as_signed_integer(8), "-1");
816        assert_eq!(F::from(32767_u128).to_string_as_signed_integer(16), "32767");
817        assert_eq!(F::from(32768_u128).to_string_as_signed_integer(16), "-32768");
818        assert_eq!(F::from(65535_u128).to_string_as_signed_integer(16), "-1");
819    }
820}
acir_field/field_element.rs

acir_field/
field_element.rs
