util/src/TclTk/tcl8.6.12/libtommath/bn_mp_reduce_2k.c

   1 #include "tommath_private.h"
   2 #ifdef BN_MP_REDUCE_2K_C
   3 /* LibTomMath, multiple-precision integer library -- Tom St Denis */
   4 /* SPDX-License-Identifier: Unlicense */
   5
   6 /* reduces a modulo n where n is of the form 2**p - d */
   7 mp_err mp_reduce_2k(mp_int *a, const mp_int *n, mp_digit d)
   8 {
   9    mp_int q;
  10    mp_err err;
  11    int    p;
  12
  13    if ((err = mp_init(&q)) != MP_OKAY) {
  14       return err;
  15    }
  16
  17    p = mp_count_bits(n);
  18 top:
  19    /* q = a/2**p, a = a mod 2**p */
  20    if ((err = mp_div_2d(a, p, &q, a)) != MP_OKAY) {
  21       goto LBL_ERR;
  22    }
  23
  24    if (d != 1u) {
  25       /* q = q * d */
  26       if ((err = mp_mul_d(&q, d, &q)) != MP_OKAY) {
  27          goto LBL_ERR;
  28       }
  29    }
  30
  31    /* a = a + q */
  32    if ((err = s_mp_add(a, &q, a)) != MP_OKAY) {
  33       goto LBL_ERR;
  34    }
  35
  36    if (mp_cmp_mag(a, n) != MP_LT) {
  37       if ((err = s_mp_sub(a, n, a)) != MP_OKAY) {
  38          goto LBL_ERR;
  39       }
  40       goto top;
  41    }
  42
  43 LBL_ERR:
  44    mp_clear(&q);
  45    return err;
  46 }
  47
  48 #endif