lib/mpi/mpi-add.c

   1 /* mpi-add.c  -  MPI functions
   2  *      Copyright (C) 1998, 1999, 2000, 2001 Free Software Foundation, Inc.
   3  *      Copyright (C) 1994, 1996 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 /****************
  33  * Add the unsigned integer V to the mpi-integer U and store the
  34  * result in W. U and V may be the same.
  35  */
  36 int mpi_add_ui(MPI w, const MPI u, unsigned long v)
  37 {
  38         mpi_ptr_t wp, up;
  39         mpi_size_t usize, wsize;
  40         int usign, wsign;
  41
  42         usize = u->nlimbs;
  43         usign = u->sign;
  44         wsign = 0;
  45
  46         /* If not space for W (and possible carry), increase space.  */
  47         wsize = usize + 1;
  48         if (w->alloced < wsize)
  49                 if (mpi_resize(w, wsize) < 0)
  50                         return -ENOMEM;
  51
  52         /* These must be after realloc (U may be the same as W).  */
  53         up = u->d;
  54         wp = w->d;
  55
  56         if (!usize) {           /* simple */
  57                 wp[0] = v;
  58                 wsize = v ? 1 : 0;
  59         } else if (!usign) {    /* mpi is not negative */
  60                 mpi_limb_t cy;
  61                 cy = mpihelp_add_1(wp, up, usize, v);
  62                 wp[usize] = cy;
  63                 wsize = usize + cy;
  64         } else {                /* The signs are different.  Need exact comparison to determine
  65                                  * which operand to subtract from which.  */
  66                 if (usize == 1 && up[0] < v) {
  67                         wp[0] = v - up[0];
  68                         wsize = 1;
  69                 } else {
  70                         mpihelp_sub_1(wp, up, usize, v);
  71                         /* Size can decrease with at most one limb. */
  72                         wsize = usize - (wp[usize - 1] == 0);
  73                         wsign = 1;
  74                 }
  75         }
  76
  77         w->nlimbs = wsize;
  78         w->sign = wsign;
  79         return 0;
  80 }
  81
  82 int mpi_add(MPI w, MPI u, MPI v)
  83 {
  84         mpi_ptr_t wp, up, vp;
  85         mpi_size_t usize, vsize, wsize;
  86         int usign, vsign, wsign;
  87
  88         if (u->nlimbs < v->nlimbs) {    /* Swap U and V. */
  89                 usize = v->nlimbs;
  90                 usign = v->sign;
  91                 vsize = u->nlimbs;
  92                 vsign = u->sign;
  93                 wsize = usize + 1;
  94                 if (RESIZE_IF_NEEDED(w, wsize) < 0)
  95                         return -ENOMEM;
  96                 /* These must be after realloc (u or v may be the same as w).  */
  97                 up = v->d;
  98                 vp = u->d;
  99         } else {
 100                 usize = u->nlimbs;
 101                 usign = u->sign;
 102                 vsize = v->nlimbs;
 103                 vsign = v->sign;
 104                 wsize = usize + 1;
 105                 if (RESIZE_IF_NEEDED(w, wsize) < 0)
 106                         return -ENOMEM;
 107                 /* These must be after realloc (u or v may be the same as w).  */
 108                 up = u->d;
 109                 vp = v->d;
 110         }
 111         wp = w->d;
 112         wsign = 0;
 113
 114         if (!vsize) {           /* simple */
 115                 MPN_COPY(wp, up, usize);
 116                 wsize = usize;
 117                 wsign = usign;
 118         } else if (usign != vsign) {    /* different sign */
 119                 /* This test is right since USIZE >= VSIZE */
 120                 if (usize != vsize) {
 121                         mpihelp_sub(wp, up, usize, vp, vsize);
 122                         wsize = usize;
 123                         MPN_NORMALIZE(wp, wsize);
 124                         wsign = usign;
 125                 } else if (mpihelp_cmp(up, vp, usize) < 0) {
 126                         mpihelp_sub_n(wp, vp, up, usize);
 127                         wsize = usize;
 128                         MPN_NORMALIZE(wp, wsize);
 129                         if (!usign)
 130                                 wsign = 1;
 131                 } else {
 132                         mpihelp_sub_n(wp, up, vp, usize);
 133                         wsize = usize;
 134                         MPN_NORMALIZE(wp, wsize);
 135                         if (usign)
 136                                 wsign = 1;
 137                 }
 138         } else {                /* U and V have same sign. Add them. */
 139                 mpi_limb_t cy = mpihelp_add(wp, up, usize, vp, vsize);
 140                 wp[usize] = cy;
 141                 wsize = usize + cy;
 142                 if (usign)
 143                         wsign = 1;
 144         }
 145
 146         w->nlimbs = wsize;
 147         w->sign = wsign;
 148         return 0;
 149 }
 150
 151 /****************
 152  * Subtract the unsigned integer V from the mpi-integer U and store the
 153  * result in W.
 154  */
 155 int mpi_sub_ui(MPI w, MPI u, unsigned long v)
 156 {
 157         mpi_ptr_t wp, up;
 158         mpi_size_t usize, wsize;
 159         int usign, wsign;
 160
 161         usize = u->nlimbs;
 162         usign = u->sign;
 163         wsign = 0;
 164
 165         /* If not space for W (and possible carry), increase space.  */
 166         wsize = usize + 1;
 167         if (w->alloced < wsize)
 168                 if (mpi_resize(w, wsize) < 0)
 169                         return -ENOMEM;
 170
 171         /* These must be after realloc (U may be the same as W).  */
 172         up = u->d;
 173         wp = w->d;
 174
 175         if (!usize) {           /* simple */
 176                 wp[0] = v;
 177                 wsize = v ? 1 : 0;
 178                 wsign = 1;
 179         } else if (usign) {     /* mpi and v are negative */
 180                 mpi_limb_t cy;
 181                 cy = mpihelp_add_1(wp, up, usize, v);
 182                 wp[usize] = cy;
 183                 wsize = usize + cy;
 184         } else {                /* The signs are different.  Need exact comparison to determine
 185                                  * which operand to subtract from which.  */
 186                 if (usize == 1 && up[0] < v) {
 187                         wp[0] = v - up[0];
 188                         wsize = 1;
 189                         wsign = 1;
 190                 } else {
 191                         mpihelp_sub_1(wp, up, usize, v);
 192                         /* Size can decrease with at most one limb. */
 193                         wsize = usize - (wp[usize - 1] == 0);
 194                 }
 195         }
 196
 197         w->nlimbs = wsize;
 198         w->sign = wsign;
 199         return 0;
 200 }
 201
 202 int mpi_sub(MPI w, MPI u, MPI v)
 203 {
 204         int rc;
 205
 206         if (w == v) {
 207                 MPI vv;
 208                 if (mpi_copy(&vv, v) < 0)
 209                         return -ENOMEM;
 210                 vv->sign = !vv->sign;
 211                 rc = mpi_add(w, u, vv);
 212                 mpi_free(vv);
 213         } else {
 214                 /* fixme: this is not thread-save (we temp. modify v) */
 215                 v->sign = !v->sign;
 216                 rc = mpi_add(w, u, v);
 217                 v->sign = !v->sign;
 218         }
 219         return rc;
 220 }
 221
 222 int mpi_addm(MPI w, MPI u, MPI v, MPI m)
 223 {
 224         if (mpi_add(w, u, v) < 0 || mpi_fdiv_r(w, w, m) < 0)
 225                 return -ENOMEM;
 226         return 0;
 227 }
 228
 229 int mpi_subm(MPI w, MPI u, MPI v, MPI m)
 230 {
 231         if (mpi_sub(w, u, v) < 0 || mpi_fdiv_r(w, w, m) < 0)
 232                 return -ENOMEM;
 233         return 0;
 234 }