/*
 * Copyright 2021 https://github.com/tlepoint
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *      http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */

#ifndef TLEPOINT_BARRETT_H
#define TLEPOINT_BARRETT_H

#include "absl/numeric/int128.h"
#include "absl/types/span.h"

// Modular reduction using Barrett reduction
// https://en.wikipedia.org/wiki/Barrett_reduction
template <typename Int>
struct Barrett {
  Barrett(Int modulus)
      : modulus(modulus),
        precomputed(static_cast<Int>(
            (static_cast<absl::uint128>(1) << (sizeof(Int) * 8)) / modulus)) {}

  std::vector<Int> Reduce(absl::Span<const Int> in) {
    std::vector<Int> out;
    out.reserve(in.size());
    std::transform(
        in.begin(), in.end(), std::back_inserter(out),
        [this](const Int &n) -> Int {
          Int q = static_cast<Int>(
              (static_cast<absl::uint128>(precomputed) * n) >> nbits);
          q = n - q * modulus;
          return (q >= modulus) ? q - modulus : q;
        });
    return out;
  }

  Int modulus;
  Int precomputed;
  static constexpr size_t nbits = sizeof(Int) * 8;
};

#endif  // TLEPOINT_BARRETT_H