Line data    Source code

       1             : #include "tommath_private.h"
       2             : #ifdef BN_MP_MONTGOMERY_CALC_NORMALIZATION_C
       3             : /* LibTomMath, multiple-precision integer library -- Tom St Denis */
       4             : /* SPDX-License-Identifier: Unlicense */
       5             : 
       6             : /*
       7             :  * shifts with subtractions when the result is greater than b.
       8             :  *
       9             :  * The method is slightly modified to shift B unconditionally upto just under
      10             :  * the leading bit of b.  This saves alot of multiple precision shifting.
      11             :  */
      12         922 : mp_err mp_montgomery_calc_normalization(mp_int *a, const mp_int *b)
      13             : {
      14          32 :    int    x, bits;
      15          32 :    mp_err err;
      16             : 
      17             :    /* how many bits of last digit does b use */
      18         922 :    bits = mp_count_bits(b) % MP_DIGIT_BIT;
      19             : 
      20         922 :    if (b->used > 1) {
      21         922 :       if ((err = mp_2expt(a, ((b->used - 1) * MP_DIGIT_BIT) + bits - 1)) != MP_OKAY) {
      22           0 :          return err;
      23             :       }
      24             :    } else {
      25           0 :       mp_set(a, 1uL);
      26           0 :       bits = 1;
      27             :    }
      28             : 
      29             : 
      30             :    /* now compute C = A * B mod b */
      31       45808 :    for (x = bits - 1; x < (int)MP_DIGIT_BIT; x++) {
      32       44886 :       if ((err = mp_mul_2(a, a)) != MP_OKAY) {
      33           0 :          return err;
      34             :       }
      35       44886 :       if (mp_cmp_mag(a, b) != MP_LT) {
      36       16764 :          if ((err = s_mp_sub(a, b, a)) != MP_OKAY) {
      37           0 :             return err;
      38             :          }
      39             :       }
      40             :    }
      41             : 
      42         890 :    return MP_OKAY;
      43             : }
      44             : #endif