lib/mpi/mpi-mul.c

   1 /* mpi-mul.c  -  MPI functions
   2  *      Copyright (C) 1994, 1996 Free Software Foundation, Inc.
   3  *      Copyright (C) 1998, 2001 Free Software Foundation, Inc.
   4  *
   5  * This file is part of GnuPG.
   6  *
   7  * GnuPG is free software; you can redistribute it and/or modify
   8  * it under the terms of the GNU General Public License as published by
   9  * the Free Software Foundation; either version 2 of the License, or
  10  * (at your option) any later version.
  11  *
  12  * GnuPG is distributed in the hope that it will be useful,
  13  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  14  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  15  * GNU General Public License for more details.
  16  *
  17  * You should have received a copy of the GNU General Public License
  18  * along with this program; if not, write to the Free Software
  19  * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA
  20  *
  21  * Note: This code is heavily based on the GNU MP Library.
  22  *       Actually it's the same code with only minor changes in the
  23  *       way the data is stored; this is to support the abstraction
  24  *       of an optional secure memory allocation which may be used
  25  *       to avoid revealing of sensitive data due to paging etc.
  26  *       The GNU MP Library itself is published under the LGPL;
  27  *       however I decided to publish this code under the plain GPL.
  28  */
  29
  30 #include "mpi-internal.h"
  31
  32 int mpi_mul_ui(MPI prod, MPI mult, unsigned long small_mult)
  33 {
  34         mpi_size_t size, prod_size;
  35         mpi_ptr_t prod_ptr;
  36         mpi_limb_t cy;
  37         int sign;
  38
  39         size = mult->nlimbs;
  40         sign = mult->sign;
  41
  42         if (!size || !small_mult) {
  43                 prod->nlimbs = 0;
  44                 prod->sign = 0;
  45                 return 0;
  46         }
  47
  48         prod_size = size + 1;
  49         if (prod->alloced < prod_size)
  50                 if (mpi_resize(prod, prod_size) < 0)
  51                         return -ENOMEM;
  52         prod_ptr = prod->d;
  53
  54         cy = mpihelp_mul_1(prod_ptr, mult->d, size, (mpi_limb_t) small_mult);
  55         if (cy)
  56                 prod_ptr[size++] = cy;
  57         prod->nlimbs = size;
  58         prod->sign = sign;
  59         return 0;
  60 }
  61
  62 int mpi_mul_2exp(MPI w, MPI u, unsigned long cnt)
  63 {
  64         mpi_size_t usize, wsize, limb_cnt;
  65         mpi_ptr_t wp;
  66         mpi_limb_t wlimb;
  67         int usign, wsign;
  68
  69         usize = u->nlimbs;
  70         usign = u->sign;
  71
  72         if (!usize) {
  73                 w->nlimbs = 0;
  74                 w->sign = 0;
  75                 return 0;
  76         }
  77
  78         limb_cnt = cnt / BITS_PER_MPI_LIMB;
  79         wsize = usize + limb_cnt + 1;
  80         if (w->alloced < wsize)
  81                 if (mpi_resize(w, wsize) < 0)
  82                         return -ENOMEM;
  83         wp = w->d;
  84         wsize = usize + limb_cnt;
  85         wsign = usign;
  86
  87         cnt %= BITS_PER_MPI_LIMB;
  88         if (cnt) {
  89                 wlimb = mpihelp_lshift(wp + limb_cnt, u->d, usize, cnt);
  90                 if (wlimb) {
  91                         wp[wsize] = wlimb;
  92                         wsize++;
  93                 }
  94         } else {
  95                 MPN_COPY_DECR(wp + limb_cnt, u->d, usize);
  96         }
  97
  98         /* Zero all whole limbs at low end.  Do it here and not before calling
  99          * mpn_lshift, not to lose for U == W.  */
 100         MPN_ZERO(wp, limb_cnt);
 101
 102         w->nlimbs = wsize;
 103         w->sign = wsign;
 104         return 0;
 105 }
 106
 107 int mpi_mul(MPI w, MPI u, MPI v)
 108 {
 109         int rc = -ENOMEM;
 110         mpi_size_t usize, vsize, wsize;
 111         mpi_ptr_t up, vp, wp;
 112         mpi_limb_t cy;
 113         int usign, vsign, sign_product;
 114         int assign_wp = 0;
 115         mpi_ptr_t tmp_limb = NULL;
 116
 117         if (u->nlimbs < v->nlimbs) {    /* Swap U and V. */
 118                 usize = v->nlimbs;
 119                 usign = v->sign;
 120                 up = v->d;
 121                 vsize = u->nlimbs;
 122                 vsign = u->sign;
 123                 vp = u->d;
 124         } else {
 125                 usize = u->nlimbs;
 126                 usign = u->sign;
 127                 up = u->d;
 128                 vsize = v->nlimbs;
 129                 vsign = v->sign;
 130                 vp = v->d;
 131         }
 132         sign_product = usign ^ vsign;
 133         wp = w->d;
 134
 135         /* Ensure W has space enough to store the result.  */
 136         wsize = usize + vsize;
 137         if (w->alloced < (size_t) wsize) {
 138                 if (wp == up || wp == vp) {
 139                         wp = mpi_alloc_limb_space(wsize);
 140                         if (!wp)
 141                                 goto nomem;
 142                         assign_wp = 1;
 143                 } else {
 144                         if (mpi_resize(w, wsize) < 0)
 145                                 goto nomem;
 146                         wp = w->d;
 147                 }
 148         } else {                /* Make U and V not overlap with W.      */
 149                 if (wp == up) {
 150                         /* W and U are identical.  Allocate temporary space for U.      */
 151                         up = tmp_limb = mpi_alloc_limb_space(usize);
 152                         if (!up)
 153                                 goto nomem;
 154                         /* Is V identical too?  Keep it identical with U.  */
 155                         if (wp == vp)
 156                                 vp = up;
 157                         /* Copy to the temporary space.  */
 158                         MPN_COPY(up, wp, usize);
 159                 } else if (wp == vp) {
 160                         /* W and V are identical.  Allocate temporary space for V.      */
 161                         vp = tmp_limb = mpi_alloc_limb_space(vsize);
 162                         if (!vp)
 163                                 goto nomem;
 164                         /* Copy to the temporary space.  */
 165                         MPN_COPY(vp, wp, vsize);
 166                 }
 167         }
 168
 169         if (!vsize)
 170                 wsize = 0;
 171         else {
 172                 if (mpihelp_mul(wp, up, usize, vp, vsize, &cy) < 0)
 173                         goto nomem;
 174                 wsize -= cy ? 0 : 1;
 175         }
 176
 177         if (assign_wp)
 178                 mpi_assign_limb_space(w, wp, wsize);
 179
 180         w->nlimbs = wsize;
 181         w->sign = sign_product;
 182         rc = 0;
 183 nomem:
 184         if (tmp_limb)
 185                 mpi_free_limb_space(tmp_limb);
 186         return rc;
 187 }
 188
 189 int mpi_mulm(MPI w, MPI u, MPI v, MPI m)
 190 {
 191         if (mpi_mul(w, u, v) < 0)
 192                 return -ENOMEM;
 193         return mpi_fdiv_r(w, w, m);
 194 }