Coverage Report

Created: 2023-02-22 06:39

`/src/botan/src/lib/math/bigint/divide.cpp`
 `Line` `Count` `Source (jump to first uncovered line)` `1` `/*` `2` `* Division Algorithms` `3` `* (C) 1999-2007,2012,2018,2021 Jack Lloyd` `4` `*` `5` `* Botan is released under the Simplified BSD License (see license.txt)` `6` `*/` `7` `8` `#include ` `9` `#include ` `10` `#include ` `11` `#include ` `12` `13` `namespace Botan {` `14` `15` `namespace {` `16` `17` `/*` `18` `* Handle signed operands, if necessary` `19` `*/` `20` `void sign_fixup(const BigInt& x, const BigInt& y, BigInt& q, BigInt& r)` `21` `695` ` {` `22` `695` ` q.cond_flip_sign(x.sign() != y.sign());` `23` `24` `695` ` if(x.is_negative() && r.is_nonzero())` `25` `123` ` {` `26` `123` ` q -= 1;` `27` `123` ` r = y.abs() - r;` `28` `123` ` }` `29` `695` ` }` `30` `31` `inline bool division_check(word q, word y2, word y1,` `32` ` word x3, word x2, word x1)` `33` `10.0k` ` {` `34` ` /*` `35` ` Compute (y3,y2,y1) = (y2,y1) * q` `36` ` and return true if (y3,y2,y1) > (x3,x2,x1)` `37` ` */` `38` `39` `10.0k` ` word y3 = 0;` `40` `10.0k` ` y1 = word_madd2(q, y1, &y3);` `41` `10.0k` ` y2 = word_madd2(q, y2, &y3);` `42` `43` `10.0k` ` const word x[3] = { x1, x2, x3 };` `44` `10.0k` ` const word y[3] = { y1, y2, y3 };` `45` `46` `10.0k` ` return bigint_ct_is_lt(x, 3, y, 3).is_set();` `47` `10.0k` ` }` `48` `49` `}` `50` `51` `void ct_divide(const BigInt& x, const BigInt& y, BigInt& q_out, BigInt& r_out)` `52` `412` ` {` `53` `412` ` if(y.is_zero())` `54` `0` ` throw Invalid_Argument("ct_divide: cannot divide by zero");` `55` `56` `412` ` const size_t x_words = x.sig_words();` `57` `412` ` const size_t y_words = y.sig_words();` `58` `59` `412` ` const size_t x_bits = x.bits();` `60` `61` `412` ` BigInt q = BigInt::with_capacity(x_words);` `62` `412` ` BigInt r = BigInt::with_capacity(y_words);` `63` `412` ` BigInt t = BigInt::with_capacity(y_words); // a temporary` `64` `65` `507k` ` for(size_t i = 0; i != x_bits; ++i)` `66` `507k` ` {` `67` `507k` ` const size_t b = x_bits - 1 - i;` `68` `507k` ` const bool x_b = x.get_bit(b);` `69` `70` `507k` ` r *= 2;` `71` `507k` ` r.conditionally_set_bit(0, x_b);` `72` `73` `507k` ` const bool r_gte_y = bigint_sub3(t.mutable_data(), r.data(), r.size(), y.data(), y_words) == 0;` `74` `75` `507k` ` q.conditionally_set_bit(b, r_gte_y);` `76` `507k` ` r.ct_cond_swap(r_gte_y, t);` `77` `507k` ` }` `78` `79` `412` ` sign_fixup(x, y, q, r);` `80` `412` ` r_out = r;` `81` `412` ` q_out = q;` `82` `412` ` }` `83` `84` `void ct_divide_word(const BigInt& x, word y, BigInt& q_out, word& r_out)` `85` `8.06k` ` {` `86` `8.06k` ` if(y == 0)` `87` `0` ` throw Invalid_Argument("ct_divide_word: cannot divide by zero");` `88` `89` `8.06k` ` const size_t x_words = x.sig_words();` `90` `8.06k` ` const size_t x_bits = x.bits();` `91` `92` `8.06k` ` BigInt q = BigInt::with_capacity(x_words);` `93` `8.06k` ` word r = 0;` `94` `95` `1.57M` ` for(size_t i = 0; i != x_bits; ++i)` `96` `1.56M` ` {` `97` `1.56M` ` const size_t b = x_bits - 1 - i;` `98` `1.56M` ` const bool x_b = x.get_bit(b);` `99` `100` `1.56M` ` const auto r_carry = CT::Mask::expand(r >> (BOTAN_MP_WORD_BITS - 1));` `101` `102` `1.56M` ` r *= 2;` `103` `1.56M` ` r += x_b;` `104` `105` `1.56M` ` const auto r_gte_y = CT::Mask::is_gte(r, y) | r_carry;` `106` `1.56M` ` q.conditionally_set_bit(b, r_gte_y.is_set());` `107` `1.56M` ` r = r_gte_y.select(r - y, r);` `108` `1.56M` ` }` `109` `110` `8.06k` ` if(x.is_negative())` `111` `0` ` {` `112` `0` ` q.flip_sign();` `113` `0` ` if(r != 0)` `114` `0` ` {` `115` `0` ` --q;` `116` `0` ` r = y - r;` `117` `0` ` }` `118` `0` ` }` `119` `120` `8.06k` ` r_out = r;` `121` `8.06k` ` q_out = q;` `122` `8.06k` ` }` `123` `124` `BigInt ct_modulo(const BigInt& x, const BigInt& y)` `125` `854` ` {` `126` `854` ` if(y.is_negative() || y.is_zero())` `127` `0` ` throw Invalid_Argument("ct_modulo requires y > 0");` `128` `129` `854` ` const size_t y_words = y.sig_words();` `130` `131` `854` ` const size_t x_bits = x.bits();` `132` `133` `854` ` BigInt r = BigInt::with_capacity(y_words);` `134` `854` ` BigInt t = BigInt::with_capacity(y_words);` `135` `136` `2.39M` ` for(size_t i = 0; i != x_bits; ++i)` `137` `2.39M` ` {` `138` `2.39M` ` const size_t b = x_bits - 1 - i;` `139` `2.39M` ` const bool x_b = x.get_bit(b);` `140` `141` `2.39M` ` r *= 2;` `142` `2.39M` ` r.conditionally_set_bit(0, x_b);` `143` `144` `2.39M` ` const bool r_gte_y = bigint_sub3(t.mutable_data(), r.data(), r.size(), y.data(), y_words) == 0;` `145` `146` `2.39M` ` r.ct_cond_swap(r_gte_y, t);` `147` `2.39M` ` }` `148` `149` `854` ` if(x.is_negative())` `150` `1` ` {` `151` `1` ` if(r.is_nonzero())` `152` `1` ` {` `153` `1` ` r = y - r;` `154` `1` ` }` `155` `1` ` }` `156` `157` `854` ` return r;` `158` `854` ` }` `159` `160` `/*` `161` `* Solve x = q * y + r` `162` `*` `163` `* See Handbook of Applied Cryptography section 14.2.5` `164` `*/` `165` `void vartime_divide(const BigInt& x, const BigInt& y_arg, BigInt& q_out, BigInt& r_out)` `166` `283` ` {` `167` `283` ` if(y_arg.is_zero())` `168` `0` ` throw Invalid_Argument("vartime_divide: cannot divide by zero");` `169` `170` `283` ` const size_t y_words = y_arg.sig_words();` `171` `172` `283` ` BOTAN_ASSERT_NOMSG(y_words > 0);` `173` `174` `283` ` BigInt y = y_arg;` `175` `176` `283` ` BigInt r = x;` `177` `283` ` BigInt q = BigInt::zero();` `178` `283` ` secure_vector ws;` `179` `180` `283` ` r.set_sign(BigInt::Positive);` `181` `283` ` y.set_sign(BigInt::Positive);` `182` `183` ` // Calculate shifts needed to normalize y with high bit set` `184` `283` ` const size_t shifts = y.top_bits_free();` `185` `186` `283` ` y <<= shifts;` `187` `283` ` r <<= shifts;` `188` `189` ` // we know y has not changed size, since we only shifted up to set high bit` `190` `283` ` const size_t t = y_words - 1;` `191` `283` ` const size_t n = std::max(y_words, r.sig_words()) - 1; // r may have changed size however` `192` `193` `283` ` BOTAN_ASSERT_NOMSG(n >= t);` `194` `195` `283` ` q.grow_to(n - t + 1);` `196` `197` `283` ` word* q_words = q.mutable_data();` `198` `199` `283` ` BigInt shifted_y = y << (BOTAN_MP_WORD_BITS * (n-t));` `200` `201` ` // Set q_{n-t} to number of times r > shifted_y` `202` `283` ` q_words[n-t] = r.reduce_below(shifted_y, ws);` `203` `204` `283` ` const word y_t0 = y.word_at(t);` `205` `283` ` const word y_t1 = y.word_at(t-1);` `206` `283` ` BOTAN_DEBUG_ASSERT((y_t0 >> (BOTAN_MP_WORD_BITS-1)) == 1);` `207` `208` `5.30k` ` for(size_t j = n; j != t; --j)` `209` `5.02k` ` {` `210` `5.02k` ` const word x_j0 = r.word_at(j);` `211` `5.02k` ` const word x_j1 = r.word_at(j-1);` `212` `5.02k` ` const word x_j2 = r.word_at(j-2);` `213` `214` `5.02k` ` word qjt = bigint_divop(x_j0, x_j1, y_t0);` `215` `216` `5.02k` ` qjt = CT::Mask::is_equal(x_j0, y_t0).select(MP_WORD_MAX, qjt);` `217` `218` ` // Per HAC 14.23, this operation is required at most twice` `219` `5.02k` ` qjt -= division_check(qjt, y_t0, y_t1, x_j0, x_j1, x_j2);` `220` `5.02k` ` qjt -= division_check(qjt, y_t0, y_t1, x_j0, x_j1, x_j2);` `221` `5.02k` ` BOTAN_DEBUG_ASSERT(division_check(qjt, y_t0, y_t1, x_j0, x_j1, x_j2) == false);` `222` `223` `5.02k` ` shifted_y >>= BOTAN_MP_WORD_BITS;` `224` ` // Now shifted_y == y << (BOTAN_MP_WORD_BITS * (j-t-1))` `225` `226` ` // TODO this sequence could be better` `227` `5.02k` ` r -= qjt * shifted_y;` `228` `5.02k` ` qjt -= r.is_negative();` `229` `5.02k` ` r += static_cast(r.is_negative()) * shifted_y;` `230` `231` `5.02k` ` q_words[j-t-1] = qjt;` `232` `5.02k` ` }` `233` `234` `283` ` r >>= shifts;` `235` `236` `283` ` sign_fixup(x, y_arg, q, r);` `237` `238` `283` ` r_out = r;` `239` `283` ` q_out = q;` `240` `283` ` }` `241` `242` `}`