1 #include "tommath_private.h"
2 #ifdef BN_MP_REDUCE_2K_C
3 /* LibTomMath, multiple-precision integer library -- Tom St Denis
4 *
5 * LibTomMath is a library that provides multiple-precision
6 * integer arithmetic as well as number theoretic functionality.
7 *
8 * The library was designed directly after the MPI library by
9 * Michael Fromberger but has been written from scratch with
10 * additional optimizations in place.
11 *
12 * SPDX-License-Identifier: Unlicense
13 */
14
15 /* reduces a modulo n where n is of the form 2**p - d */
mp_reduce_2k(mp_int * a,const mp_int * n,mp_digit d)16 int mp_reduce_2k(mp_int *a, const mp_int *n, mp_digit d)
17 {
18 mp_int q;
19 int p, res;
20
21 if ((res = mp_init(&q)) != MP_OKAY) {
22 return res;
23 }
24
25 p = mp_count_bits(n);
26 top:
27 /* q = a/2**p, a = a mod 2**p */
28 if ((res = mp_div_2d(a, p, &q, a)) != MP_OKAY) {
29 goto LBL_ERR;
30 }
31
32 if (d != 1u) {
33 /* q = q * d */
34 if ((res = mp_mul_d(&q, d, &q)) != MP_OKAY) {
35 goto LBL_ERR;
36 }
37 }
38
39 /* a = a + q */
40 if ((res = s_mp_add(a, &q, a)) != MP_OKAY) {
41 goto LBL_ERR;
42 }
43
44 if (mp_cmp_mag(a, n) != MP_LT) {
45 if ((res = s_mp_sub(a, n, a)) != MP_OKAY) {
46 goto LBL_ERR;
47 }
48 goto top;
49 }
50
51 LBL_ERR:
52 mp_clear(&q);
53 return res;
54 }
55
56 #endif
57
58 /* ref: $Format:%D$ */
59 /* git commit: $Format:%H$ */
60 /* commit time: $Format:%ai$ */
61