mp_reduce_is_2k.c

   1 #include "tommath_private.h"
   2 #ifdef MP_REDUCE_IS_2K_C
   3 /* LibTomMath, multiple-precision integer library -- Tom St Denis */
   4 /* SPDX-License-Identifier: Unlicense */
   5
   6 /* determines if mp_reduce_2k can be used */
   7 bool mp_reduce_is_2k(const mp_int *a)
   8 {
   9    if (mp_iszero(a)) {
  10       return false;
  11    } else if (a->used == 1) {
  12       return true;
  13    } else if (a->used > 1) {
  14       int ix, iy, iw = 1;
  15       mp_digit iz;
  16       /* Algorithm as implemented does not work if the least significant digit is zero */
  17       iz = a->dp[0] & MP_MASK;
  18       if (iz == 0u) {
  19          return false;
  20       }
  21
  22       iy = mp_count_bits(a);
  23       iz = 1;
  24       /* Test every bit from the second digit up, must be 1 */
  25       for (ix = MP_DIGIT_BIT; ix < iy; ix++) {
  26          if ((a->dp[iw] & iz) == 0u) {
  27             return false;
  28          }
  29          iz <<= 1;
  30          if (iz > MP_DIGIT_MAX) {
  31             ++iw;
  32             iz = 1;
  33          }
  34       }
  35       return true;
  36    } else {
  37       return true;
  38    }
  39 }
  40
  41 #endif