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