text: use crate::{
      prelude::{AffineCurve, BigInteger, FpParameters, One, PrimeField, ProjectiveCurve, Zero},
      Vec,
  };
  #[cfg(feature = "parallel")]
  use rayon::prelude::*;
  
  pub struct VariableBaseMSM;
  
  impl VariableBaseMSM {
      fn msm_inner<G: AffineCurve>(
          bases: &[G],
          scalars: &[<G::ScalarField as PrimeField>::BigInt],
      ) -> G::Projective
      where
          G::Projective: ProjectiveCurve<Affine = G>,
      {
          let c = if scalars.len() < 32 {
              3
          } else {
              super::ln_without_floats(scalars.len()) + 2
          };
  
          let num_bits = <G::ScalarField as PrimeField>::Params::MODULUS_BITS as usize;
          let fr_one = G::ScalarField::one().into_repr();
  
          let zero = G::Projective::zero();
          let window_starts: Vec<_> = (0..num_bits).step_by(c).collect();
  
          #[cfg(feature = "parallel")]
          let window_starts_iter = window_starts.into_par_iter();
          #[cfg(not(feature = "parallel"))]
          let window_starts_iter = window_starts.into_iter();
  
          // Each window is of size `c`.
          // We divide up the bits 0..num_bits into windows of size `c`, and
          // in parallel process each such window.
          let window_sums: Vec<_> = window_starts_iter
              .map(|w_start| {
                  let mut res = zero;
                  // We don't need the "zero" bucket, so we only have 2^c - 1 buckets
                  let mut buckets = vec![zero; (1 << c) - 1];
                  scalars
                      .iter()
                      .zip(bases)
                      .filter(|(s, _)| !s.is_zero())
                      .for_each(|(&scalar, base)| {
                          if scalar == fr_one {
                              // We only process unit scalars once in the first window.
                              if w_start == 0 {
                                  res.add_assign_mixed(base);
                              }
                          } else {
                              let mut scalar = scalar;
  
                              // We right-shift by w_start, thus getting rid of the
                              // lower bits.
                              scalar.divn(w_start as u32);
  
                              // We mod the remaining bits by the window size.
                              let scalar = scalar.as_ref()[0] % (1 << c);
  
                              // If the scalar is non-zero, we update the corresponding
                              // bucket.
                              // (Recall that `buckets` doesn't have a zero bucket.)
                              if scalar != 0 {
                                  buckets[(scalar - 1) as usize].add_assign_mixed(base);
                              }
                          }
                      });
                  let buckets = G::Projective::batch_normalization_into_affine(&buckets);
  
                  let mut running_sum = G::Projective::zero();
                  for b in buckets.into_iter().rev() {
                      running_sum.add_assign_mixed(&b);
                      res += running_sum;
                  }
  
                  res
              })
              .collect();
  
          // We store the sum for the lowest window.
          let lowest = *window_sums.first().unwrap();
  
          // We're traversing windows from high to low.
          lowest
              + window_sums[1..]
                  .iter()
                  .rev()
                  .fold(zero, |mut total, sum_i| {
                      total += sum_i;
                      for _ in 0..c {
                          total.double_in_place();
                      }
                      total
                  })
      }
  
      pub fn multi_scalar_mul<G: AffineCurve>(
          bases: &[G],
          scalars: &[<G::ScalarField as PrimeField>::BigInt],
      ) -> G::Projective {
          Self::msm_inner(bases, scalars)
      }
  }
  