mp_div_d.c

   1 #include "tommath_private.h"
   2 #ifdef MP_DIV_D_C
   3 /* LibTomMath, multiple-precision integer library -- Tom St Denis */
   4 /* SPDX-License-Identifier: Unlicense */
   5
   6 /* single digit division (based on routine from MPI) */
   7 mp_err mp_div_d(const mp_int *a, mp_digit b, mp_int *c, mp_digit *d)
   8 {
   9    mp_int  q;
  10    mp_word w;
  11    mp_err err;
  12    int ix;
  13
  14    /* cannot divide by zero */
  15    if (b == 0u) {
  16       return MP_VAL;
  17    }
  18
  19    /* quick outs */
  20    if ((b == 1u) || mp_iszero(a)) {
  21       if (d != NULL) {
  22          *d = 0;
  23       }
  24       if (c != NULL) {
  25          return mp_copy(a, c);
  26       }
  27       return MP_OKAY;
  28    }
  29
  30    /* power of two ? */
  31    if (MP_HAS(MP_DIV_2) && (b == 2u)) {
  32       if (d != NULL) {
  33          *d = mp_isodd(a) ? 1u : 0u;
  34       }
  35       return (c == NULL) ? MP_OKAY : mp_div_2(a, c);
  36    }
  37    if (MP_HAS(MP_DIV_2D) && MP_IS_2EXPT(b)) {
  38       ix = 1;
  39       while ((ix < MP_DIGIT_BIT) && (b != (((mp_digit)1)<<ix))) {
  40          ix++;
  41       }
  42       if (d != NULL) {
  43          *d = a->dp[0] & (((mp_digit)1<<(mp_digit)ix) - 1uL);
  44       }
  45       return (c == NULL) ? MP_OKAY : mp_div_2d(a, ix, c, NULL);
  46    }
  47
  48    /* three? */
  49    if (MP_HAS(S_MP_DIV_3) && (b == 3u)) {
  50       return s_mp_div_3(a, c, d);
  51    }
  52
  53    /* no easy answer [c'est la vie].  Just division */
  54    if ((err = mp_init_size(&q, a->used)) != MP_OKAY) {
  55       return err;
  56    }
  57
  58    q.used = a->used;
  59    q.sign = a->sign;
  60    w = 0;
  61    for (ix = a->used; ix --> 0;) {
  62       mp_digit t = 0;
  63       w = (w << (mp_word)MP_DIGIT_BIT) | (mp_word)a->dp[ix];
  64       if (w >= b) {
  65          t = (mp_digit)(w / b);
  66          w -= (mp_word)t * (mp_word)b;
  67       }
  68       q.dp[ix] = t;
  69    }
  70
  71    if (d != NULL) {
  72       *d = (mp_digit)w;
  73    }
  74
  75    if (c != NULL) {
  76       mp_clamp(&q);
  77       mp_exch(&q, c);
  78    }
  79    mp_clear(&q);
  80
  81    return MP_OKAY;
  82 }
  83
  84 #endif