s_mp_mul_balance.c

   1 #include "tommath_private.h"
   2 #ifdef S_MP_MUL_BALANCE_C
   3 /* LibTomMath, multiple-precision integer library -- Tom St Denis */
   4 /* SPDX-License-Identifier: Unlicense */
   5
   6 /* single-digit multiplication with the smaller number as the single-digit */
   7 mp_err s_mp_mul_balance(const mp_int *a, const mp_int *b, mp_int *c)
   8 {
   9    mp_int a0, tmp, r;
  10    mp_err err;
  11    int i, j,
  12        nblocks = MP_MAX(a->used, b->used) / MP_MIN(a->used, b->used),
  13        bsize = MP_MIN(a->used, b->used);
  14
  15    if ((err = mp_init_size(&a0, bsize + 2)) != MP_OKAY) {
  16       return err;
  17    }
  18    if ((err = mp_init_multi(&tmp, &r, NULL)) != MP_OKAY) {
  19       mp_clear(&a0);
  20       return err;
  21    }
  22
  23    /* Make sure that A is the larger one*/
  24    if (a->used < b->used) {
  25       MP_EXCH(const mp_int *, a, b);
  26    }
  27
  28    for (i = 0, j=0; i < nblocks; i++) {
  29       /* Cut a slice off of a */
  30       a0.used = bsize;
  31       s_mp_copy_digs(a0.dp, a->dp + j, a0.used);
  32       j += a0.used;
  33       mp_clamp(&a0);
  34
  35       /* Multiply with b */
  36       if ((err = mp_mul(&a0, b, &tmp)) != MP_OKAY) {
  37          goto LBL_ERR;
  38       }
  39       /* Shift tmp to the correct position */
  40       if ((err = mp_lshd(&tmp, bsize * i)) != MP_OKAY) {
  41          goto LBL_ERR;
  42       }
  43       /* Add to output. No carry needed */
  44       if ((err = mp_add(&r, &tmp, &r)) != MP_OKAY) {
  45          goto LBL_ERR;
  46       }
  47    }
  48    /* The left-overs; there are always left-overs */
  49    if (j < a->used) {
  50       a0.used = a->used - j;
  51       s_mp_copy_digs(a0.dp, a->dp + j, a0.used);
  52       j += a0.used;
  53       mp_clamp(&a0);
  54
  55       if ((err = mp_mul(&a0, b, &tmp)) != MP_OKAY) {
  56          goto LBL_ERR;
  57       }
  58       if ((err = mp_lshd(&tmp, bsize * i)) != MP_OKAY) {
  59          goto LBL_ERR;
  60       }
  61       if ((err = mp_add(&r, &tmp, &r)) != MP_OKAY) {
  62          goto LBL_ERR;
  63       }
  64    }
  65
  66    mp_exch(&r,c);
  67 LBL_ERR:
  68    mp_clear_multi(&a0, &tmp, &r,NULL);
  69    return err;
  70 }
  71 #endif