Line data    Source code

       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           0 : 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           0 :    if ((err = mp_init(&q)) != MP_OKAY) {
      14           0 :       return err;
      15             :    }
      16             : 
      17           0 :    p = mp_count_bits(n);
      18           0 : top:
      19             :    /* q = a/2**p, a = a mod 2**p */
      20           0 :    if ((err = mp_div_2d(a, p, &q, a)) != MP_OKAY) {
      21           0 :       goto LBL_ERR;
      22             :    }
      23             : 
      24           0 :    if (d != 1u) {
      25             :       /* q = q * d */
      26           0 :       if ((err = mp_mul_d(&q, d, &q)) != MP_OKAY) {
      27           0 :          goto LBL_ERR;
      28             :       }
      29             :    }
      30             : 
      31             :    /* a = a + q */
      32           0 :    if ((err = s_mp_add(a, &q, a)) != MP_OKAY) {
      33           0 :       goto LBL_ERR;
      34             :    }
      35             : 
      36           0 :    if (mp_cmp_mag(a, n) != MP_LT) {
      37           0 :       if ((err = s_mp_sub(a, n, a)) != MP_OKAY) {
      38           0 :          goto LBL_ERR;
      39             :       }
      40           0 :       goto top;
      41             :    }
      42             : 
      43           0 : LBL_ERR:
      44           0 :    mp_clear(&q);
      45           0 :    return err;
      46             : }
      47             : 
      48             : #endif