Botan::divide_precomp< W > Class Template Reference

#include <mp_core.h>

Public Member Functions
constexpr	divide_precomp (W divisor)
constexpr W	vartime_div_2to1 (W n1, W n0) const
constexpr W	vartime_mod_2to1 (W n1, W n0) const

Detailed Description

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

Setup for variable-time word level division/modulo operations

Currently this just uses the compiler's support for a 2/1 word division, but likely could be improved by precomputed values based on the divisor, for example using the approaches outlined in Hacker's Delight chapter 10.

Definition at line 559 of file mp_core.h.

Constructor & Destructor Documentation

divide_precomp()

template<WordType W>

Botan::divide_precomp< W >::divide_precomp ( W divisor )

inlineexplicitconstexpr

Definition at line 561 of file mp_core.h.

                                                   : m_divisor(divisor) {
         BOTAN_ARG_CHECK(m_divisor != 0, "Division by zero");
      }

References BOTAN_ARG_CHECK.

Member Function Documentation

vartime_div_2to1()

template<WordType W>

W Botan::divide_precomp< W >::vartime_div_2to1 ( W n1, W n0 ) const

inlineconstexpr

Definition at line 568 of file mp_core.h.

                                                            {
         BOTAN_ASSERT_NOMSG(n1 < m_divisor);
 
         if(m_divisor == WordInfo<W>::max) {
            return vartime_div_2to1_max_d(n1, n0);
         }
 
         if(m_divisor == WordInfo<W>::top_bit) {
            // Simply a shift by N-1 bits
            return (n1 << 1) | (n0 >> (WordInfo<W>::bits - 1));
         }
 
         if(!std::is_constant_evaluated()) {
#if defined(BOTAN_MP_USE_X86_64_ASM)
            if constexpr(std::same_as<W, uint64_t>) {
               W quotient = 0;
               W remainder = 0;
               // NOLINTNEXTLINE(*-no-assembler)
               asm("divq %[v]" : "=a"(quotient), "=d"(remainder) : [v] "r"(m_divisor), "a"(n0), "d"(n1));
               return quotient;
            }
#endif
 
#if !defined(BOTAN_BUILD_COMPILER_IS_CLANGCL)
 
            /* clang-cl has a bug where on encountering a 128/64 division it emits
            * a call to __udivti3() but then fails to link the relevant builtin into
            * the binary, causing a link failure. Work around this by simply omitting
            * such code for clang-cl
            *
            * See https://github.com/llvm/llvm-project/issues/25679
            */
            if constexpr(WordInfo<W>::dword_is_native) {
               typename WordInfo<W>::dword n = n1;
               n <<= WordInfo<W>::bits;
               n |= n0;
               return static_cast<W>(n / m_divisor);
            }
#endif
         }
 
         W high = n1;
         W quotient = 0;
 
         for(size_t i = 0; i != WordInfo<W>::bits; ++i) {
            const W high_top_bit = high >> (WordInfo<W>::bits - 1);
 
            high <<= 1;
            high |= (n0 >> (WordInfo<W>::bits - 1 - i)) & 1;
            quotient <<= 1;
 
            if(high_top_bit || high >= m_divisor) {
               high -= m_divisor;
               quotient |= 1;
            }
         }
 
         return quotient;
      }

References BOTAN_ASSERT_NOMSG.

Referenced by Botan::vartime_divide(), Botan::vartime_divide_pow2k(), and vartime_mod_2to1().

vartime_mod_2to1()

template<WordType W>

W Botan::divide_precomp< W >::vartime_mod_2to1 ( W n1, W n0 ) const

inlineconstexpr

Definition at line 631 of file mp_core.h.

                                                            {
         BOTAN_ASSERT_NOMSG(n1 < m_divisor);
         W q = this->vartime_div_2to1(n1, n0);
         W carry = 0;
         q = word_madd2(q, m_divisor, &carry);
         return (n0 - q);
      }

References BOTAN_ASSERT_NOMSG, Botan::carry(), vartime_div_2to1(), and Botan::word_madd2().

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

---

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

• src/lib/math/mp/mp_core.h