Botan 3.14.1
Crypto and TLS for C&
Botan::divide_precomp< W > Class Template Referencefinal

#include <mp_core.h>

Public Member Functions

constexpr W div_2to1 (W n1, W n0) const
constexpr std::pair< W, W > divmod_2to1_ct (W n1, W n0) const
constexpr std::pair< W, W > divmod_2to1_vartime (W n1, W n0) const
constexpr W mod_2to1 (W n1, W n0) const
constexpr W reciprocal () const

Static Public Member Functions

static constexpr divide_precomp setup (W divisor)
static constexpr divide_precomp setup_vartime (W divisor)
static constexpr divide_precomp setup_with_reciprocal (W divisor, W reciprocal)

Detailed Description

template<WordType W>
class Botan::divide_precomp< W >

Setup for word level division/modulo operations

The general case uses a reciprocal of the normalized divisor, precomputed at construction time, following Algorithm 4 of Möller and Granlund "Improved Division by Invariant Integers" (IEEE Trans. Computers, 2011).

The 2/1 division operations run in constant time with respect to the numerator. The divisor is treated as public; construction and the choice of code path are variable time in it.

Definition at line 684 of file mp_core.h.

Member Function Documentation

◆ div_2to1()

template<WordType W>
W Botan::divide_precomp< W >::div_2to1 ( W n1,
W n0 ) const
inlineconstexpr

Definition at line 770 of file mp_core.h.

770{ return this->divmod_2to1_vartime(n1, n0).first; }
constexpr std::pair< W, W > divmod_2to1_vartime(W n1, W n0) const
Definition mp_core.h:719

References divmod_2to1_vartime().

◆ divmod_2to1_ct()

template<WordType W>
std::pair< W, W > Botan::divide_precomp< W >::divmod_2to1_ct ( W n1,
W n0 ) const
inlineconstexpr

Definition at line 741 of file mp_core.h.

741 {
742 /*
743 * Scale the numerator to match the normalized divisor; the scaling cancels
744 * in the quotient and is removed from the remainder by the final shift.
745 */
746 n1 <<= m_shift;
747 const size_t rshift = WordInfo<W>::bits - m_shift;
748 /*
749 * We can't just `n0 >> rshift` because m_shift may be 0 (high bit divisor)
750 * in which case rshift will be the maximum bit length, and >> by the maximum
751 * bitlength is undefined behavior despite having an entirely obvious meaning.
752 *
753 * However we know m_shift is not equal to the bit length of the word, because
754 * that would imply that the divisor is 0. Thus rshift must be >= 1. So split
755 * the shift into two phases (first rshift-1, then 1)
756 */
757 n1 |= (n0 >> 1) >> (rshift - 1);
758 n0 <<= m_shift;
759
760 const auto [q, scaled_r] = div2by1_preinv(n1, n0, m_norm_divisor, m_reciprocal);
761 const W r = scaled_r >> m_shift;
762 return std::make_pair(q, r);
763 }

Referenced by divmod_2to1_vartime().

◆ divmod_2to1_vartime()

template<WordType W>
std::pair< W, W > Botan::divide_precomp< W >::divmod_2to1_vartime ( W n1,
W n0 ) const
inlineconstexpr

Definition at line 719 of file mp_core.h.

719 {
720 if(m_divisor == WordInfo<W>::max) {
721 const W q = div_2to1_max_d(n1, n0);
722 const W r = static_cast<W>(n0 + q);
723 return std::make_pair(q, r);
724 }
725
726 if(m_divisor == WordInfo<W>::top_bit) {
727 // Simply a shift by N-1 bits
728 const W q = (n1 << 1) | (n0 >> (WordInfo<W>::bits - 1));
729 const W r = static_cast<W>(n0 & (WordInfo<W>::top_bit - 1));
730 return std::make_pair(q, r);
731 }
732
733 return divmod_2to1_ct(n1, n0);
734 }
constexpr std::pair< W, W > divmod_2to1_ct(W n1, W n0) const
Definition mp_core.h:741

References divmod_2to1_ct().

Referenced by div_2to1(), and mod_2to1().

◆ mod_2to1()

template<WordType W>
W Botan::divide_precomp< W >::mod_2to1 ( W n1,
W n0 ) const
inlineconstexpr

Definition at line 777 of file mp_core.h.

777{ return this->divmod_2to1_vartime(n1, n0).second; }

References divmod_2to1_vartime().

◆ reciprocal()

template<WordType W>
W Botan::divide_precomp< W >::reciprocal ( ) const
inlineconstexpr

Definition at line 709 of file mp_core.h.

709{ return m_reciprocal; }

Referenced by setup(), setup_vartime(), and setup_with_reciprocal().

◆ setup()

template<WordType W>
constexpr divide_precomp Botan::divide_precomp< W >::setup ( W divisor)
inlinestaticconstexpr

Definition at line 695 of file mp_core.h.

695 {
696 const size_t shift = WordInfo<W>::bits - high_bit(divisor);
697 const W norm_divisor = divisor << shift;
699 return divide_precomp(divisor, shift, norm_divisor, reciprocal);
700 }
constexpr W reciprocal() const
Definition mp_core.h:709
constexpr W reciprocal_word_ct(W D)
Definition mp_core.h:650
BOTAN_FORCE_INLINE constexpr size_t high_bit(T n)
Definition bit_ops.h:73

References Botan::high_bit(), reciprocal(), and Botan::reciprocal_word_ct().

Referenced by Botan::BigInt::to_dec_string().

◆ setup_vartime()

template<WordType W>
constexpr divide_precomp Botan::divide_precomp< W >::setup_vartime ( W divisor)
inlinestaticconstexpr

Definition at line 687 of file mp_core.h.

687 {
688 const size_t shift = WordInfo<W>::bits - high_bit(divisor);
689 const W norm_divisor = divisor << shift;
691 return divide_precomp(divisor, shift, norm_divisor, reciprocal);
692 }
constexpr W reciprocal_word(W D)
Definition mp_core.h:578

References Botan::high_bit(), reciprocal(), and Botan::reciprocal_word().

Referenced by Botan::ct_divide_word(), Botan::ct_mod_word(), Botan::operator%(), and Botan::BigInt::operator%=().

◆ setup_with_reciprocal()

template<WordType W>
constexpr divide_precomp Botan::divide_precomp< W >::setup_with_reciprocal ( W divisor,
W reciprocal )
inlinestaticconstexpr

Definition at line 703 of file mp_core.h.

703 {
704 // The divisor is public so a variable time count is fine
705 const size_t shift = std::countl_zero(divisor);
706 return divide_precomp(divisor, shift, divisor << shift, reciprocal);
707 }

References reciprocal().


The documentation for this class was generated from the following file: