1  // Copyright (c) 2019-2025 Alpha-Delta Network Inc.
  2  // This file is part of the deltavm library.
  3  
  4  // Licensed under the Apache License, Version 2.0 (the "License");
  5  // you may not use this file except in compliance with the License.
  6  // You may obtain a copy of the License at:
  7  
  8  // http://www.apache.org/licenses/LICENSE-2.0
  9  
 10  // Unless required by applicable law or agreed to in writing, software
 11  // distributed under the License is distributed on an "AS IS" BASIS,
 12  // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 13  // See the License for the specific language governing permissions and
 14  // limitations under the License.
 15  
 16  #![allow(clippy::module_inception)]
 17  #![forbid(unsafe_code)]
 18  
 19  #[macro_use]
 20  extern crate thiserror;
 21  
 22  #[macro_use]
 23  mod macros;
 24  
 25  pub mod errors;
 26  pub use errors::*;
 27  
 28  mod fp_256;
 29  pub use fp_256::*;
 30  
 31  mod fp_384;
 32  pub use fp_384::*;
 33  
 34  mod fp2;
 35  pub use fp2::*;
 36  
 37  pub mod fp6_3over2;
 38  
 39  mod fp12_2over3over2;
 40  pub use fp12_2over3over2::*;
 41  
 42  mod legendre;
 43  pub use legendre::*;
 44  
 45  mod to_field_vec;
 46  #[allow(unused_imports)]
 47  pub use to_field_vec::*;
 48  
 49  pub mod traits;
 50  pub use traits::*;
 51  
 52  use deltavm_utilities::{
 53      FromBytes,
 54      ToBytes,
 55      biginteger::*,
 56      serialize::{CanonicalDeserialize, CanonicalDeserializeWithFlags, CanonicalSerialize, CanonicalSerializeWithFlags},
 57  };
 58  
 59  impl_field_to_biginteger!(Fp256, BigInteger256, Fp256Parameters);
 60  impl_field_to_biginteger!(Fp384, BigInteger384, Fp384Parameters);
 61  
 62  impl_primefield_serializer!(Fp256, Fp256Parameters, 32);
 63  impl_primefield_serializer!(Fp384, Fp384Parameters, 48);
 64  
 65  // Given a vector of field elements {v_i}, compute the vector {v_i^(-1)}
 66  pub fn batch_inversion<F: Field>(v: &mut [F]) {
 67      batch_inversion_and_mul(v, &F::one());
 68  }
 69  
 70  #[cfg(feature = "serial")]
 71  // Given a vector of field elements {v_i}, compute the vector {coeff * v_i^(-1)}
 72  pub fn batch_inversion_and_mul<F: Field>(v: &mut [F], coeff: &F) {
 73      serial_batch_inversion_and_mul(v, coeff);
 74  }
 75  
 76  #[cfg(not(feature = "serial"))]
 77  // Given a vector of field elements {v_i}, compute the vector {coeff * v_i^(-1)}
 78  pub fn batch_inversion_and_mul<F: Field>(v: &mut [F], coeff: &F) {
 79      use rayon::prelude::*;
 80      // Divide the vector v evenly between all available cores
 81      let min_elements_per_thread = 1;
 82      let num_cpus_available = deltavm_utilities::parallel::max_available_threads();
 83      let num_elems = v.len();
 84      let num_elem_per_thread = min_elements_per_thread.max(num_elems / num_cpus_available);
 85  
 86      // Batch invert in parallel, without copying the vector
 87      v.par_chunks_mut(num_elem_per_thread).for_each(|chunk| {
 88          serial_batch_inversion_and_mul(chunk, coeff);
 89      });
 90  }
 91  
 92  /// Given a vector of field elements {v_i}, compute the vector {coeff * v_i^(-1)}.
 93  /// This method is explicitly single-threaded.
 94  fn serial_batch_inversion_and_mul<F: Field>(v: &mut [F], coeff: &F) {
 95      // Montgomery’s Trick and Fast Implementation of Masked AES
 96      // Genelle, Prouff and Quisquater
 97      // Section 3.2
 98      // but with an optimization to multiply every element in the returned vector by
 99      // coeff
100  
101      // First pass: compute [a, ab, abc, ...]
102      let mut prod = Vec::with_capacity(v.len());
103      let mut tmp = F::one();
104      for f in v.iter().filter(|f| !f.is_zero()) {
105          tmp.mul_assign(f);
106          prod.push(tmp);
107      }
108  
109      // Invert `tmp`.
110      tmp = tmp.inverse().unwrap(); // Guaranteed to be nonzero.
111  
112      // Multiply product by coeff, so all inverses will be scaled by coeff
113      tmp *= coeff;
114  
115      // Second pass: iterate backwards to compute inverses
116      for (f, s) in v.iter_mut()
117          // Backwards
118          .rev()
119          // Ignore normalized elements
120          .filter(|f| !f.is_zero())
121          // Backwards, skip last element, fill in one for last term.
122          .zip(prod.into_iter().rev().skip(1).chain(Some(F::one())))
123      {
124          // tmp := tmp * f; f := tmp * s = 1/f
125          let new_tmp = tmp * *f;
126          *f = tmp * s;
127          tmp = new_tmp;
128      }
129  }