s_mp_div_small.c

   1 #include "tommath_private.h"
   2 #ifdef S_MP_DIV_SMALL_C
   3 /* LibTomMath, multiple-precision integer library -- Tom St Denis */
   4 /* SPDX-License-Identifier: Unlicense */
   5
   6 /* slower bit-bang division... also smaller */
   7 mp_err s_mp_div_small(const mp_int *a, const mp_int *b, mp_int *c, mp_int *d)
   8 {
   9    mp_int ta, tb, tq, q;
  10    int n;
  11    bool neg;
  12    mp_err err;
  13
  14    /* init our temps */
  15    if ((err = mp_init_multi(&ta, &tb, &tq, &q, NULL)) != MP_OKAY) {
  16       return err;
  17    }
  18
  19    mp_set(&tq, 1uL);
  20    n = mp_count_bits(a) - mp_count_bits(b);
  21    if ((err = mp_abs(a, &ta)) != MP_OKAY)                         goto LBL_ERR;
  22    if ((err = mp_abs(b, &tb)) != MP_OKAY)                         goto LBL_ERR;
  23    if ((err = mp_mul_2d(&tb, n, &tb)) != MP_OKAY)                 goto LBL_ERR;
  24    if ((err = mp_mul_2d(&tq, n, &tq)) != MP_OKAY)                 goto LBL_ERR;
  25
  26    while (n-- >= 0) {
  27       if (mp_cmp(&tb, &ta) != MP_GT) {
  28          if ((err = mp_sub(&ta, &tb, &ta)) != MP_OKAY)            goto LBL_ERR;
  29          if ((err = mp_add(&q, &tq, &q)) != MP_OKAY)              goto LBL_ERR;
  30       }
  31       if ((err = mp_div_2d(&tb, 1, &tb, NULL)) != MP_OKAY)        goto LBL_ERR;
  32       if ((err = mp_div_2d(&tq, 1, &tq, NULL)) != MP_OKAY)        goto LBL_ERR;
  33    }
  34
  35    /* now q == quotient and ta == remainder */
  36
  37    neg = (a->sign != b->sign);
  38    if (c != NULL) {
  39       mp_exch(c, &q);
  40       c->sign = ((neg && !mp_iszero(c)) ? MP_NEG : MP_ZPOS);
  41    }
  42    if (d != NULL) {
  43       mp_exch(d, &ta);
  44       d->sign = (mp_iszero(d) ? MP_ZPOS : a->sign);
  45    }
  46 LBL_ERR:
  47    mp_clear_multi(&ta, &tb, &tq, &q, NULL);
  48    return err;
  49 }
  50
  51 #endif