LXR linux/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 */
  36int 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
  82int 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 */
 155int 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
 202int 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
 222int 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
 229int 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}
 235