lib/mpi/mpi-add.c

0001 /* mpi-add.c  -  MPI functions
0002  * Copyright (C) 1994, 1996, 1998, 2001, 2002,
0003  *               2003 Free Software Foundation, Inc.
0004  *
0005  * This file is part of Libgcrypt.
0006  *
0007  * Note: This code is heavily based on the GNU MP Library.
0008  *   Actually it's the same code with only minor changes in the
0009  *   way the data is stored; this is to support the abstraction
0010  *   of an optional secure memory allocation which may be used
0011  *   to avoid revealing of sensitive data due to paging etc.
0012  */
0013
0014 #include "mpi-internal.h"
0015
0016 /****************
0017  * Add the unsigned integer V to the mpi-integer U and store the
0018  * result in W. U and V may be the same.
0019  */
0020 void mpi_add_ui(MPI w, MPI u, unsigned long v)
0021 {
0022     mpi_ptr_t wp, up;
0023     mpi_size_t usize, wsize;
0024     int usign, wsign;
0025
0026     usize = u->nlimbs;
0027     usign = u->sign;
0028     wsign = 0;
0029
0030     /* If not space for W (and possible carry), increase space.  */
0031     wsize = usize + 1;
0032     if (w->alloced < wsize)
0033         mpi_resize(w, wsize);
0034
0035     /* These must be after realloc (U may be the same as W).  */
0036     up = u->d;
0037     wp = w->d;
0038
0039     if (!usize) {  /* simple */
0040         wp[0] = v;
0041         wsize = v ? 1:0;
0042     } else if (!usign) {  /* mpi is not negative */
0043         mpi_limb_t cy;
0044         cy = mpihelp_add_1(wp, up, usize, v);
0045         wp[usize] = cy;
0046         wsize = usize + cy;
0047     } else {
0048         /* The signs are different.  Need exact comparison to determine
0049          * which operand to subtract from which.
0050          */
0051         if (usize == 1 && up[0] < v) {
0052             wp[0] = v - up[0];
0053             wsize = 1;
0054         } else {
0055             mpihelp_sub_1(wp, up, usize, v);
0056             /* Size can decrease with at most one limb. */
0057             wsize = usize - (wp[usize-1] == 0);
0058             wsign = 1;
0059         }
0060     }
0061
0062     w->nlimbs = wsize;
0063     w->sign   = wsign;
0064 }
0065
0066
0067 void mpi_add(MPI w, MPI u, MPI v)
0068 {
0069     mpi_ptr_t wp, up, vp;
0070     mpi_size_t usize, vsize, wsize;
0071     int usign, vsign, wsign;
0072
0073     if (u->nlimbs < v->nlimbs) { /* Swap U and V. */
0074         usize = v->nlimbs;
0075         usign = v->sign;
0076         vsize = u->nlimbs;
0077         vsign = u->sign;
0078         wsize = usize + 1;
0079         RESIZE_IF_NEEDED(w, wsize);
0080         /* These must be after realloc (u or v may be the same as w).  */
0081         up = v->d;
0082         vp = u->d;
0083     } else {
0084         usize = u->nlimbs;
0085         usign = u->sign;
0086         vsize = v->nlimbs;
0087         vsign = v->sign;
0088         wsize = usize + 1;
0089         RESIZE_IF_NEEDED(w, wsize);
0090         /* These must be after realloc (u or v may be the same as w).  */
0091         up = u->d;
0092         vp = v->d;
0093     }
0094     wp = w->d;
0095     wsign = 0;
0096
0097     if (!vsize) {  /* simple */
0098         MPN_COPY(wp, up, usize);
0099         wsize = usize;
0100         wsign = usign;
0101     } else if (usign != vsign) { /* different sign */
0102         /* This test is right since USIZE >= VSIZE */
0103         if (usize != vsize) {
0104             mpihelp_sub(wp, up, usize, vp, vsize);
0105             wsize = usize;
0106             MPN_NORMALIZE(wp, wsize);
0107             wsign = usign;
0108         } else if (mpihelp_cmp(up, vp, usize) < 0) {
0109             mpihelp_sub_n(wp, vp, up, usize);
0110             wsize = usize;
0111             MPN_NORMALIZE(wp, wsize);
0112             if (!usign)
0113                 wsign = 1;
0114         } else {
0115             mpihelp_sub_n(wp, up, vp, usize);
0116             wsize = usize;
0117             MPN_NORMALIZE(wp, wsize);
0118             if (usign)
0119                 wsign = 1;
0120         }
0121     } else { /* U and V have same sign. Add them. */
0122         mpi_limb_t cy = mpihelp_add(wp, up, usize, vp, vsize);
0123         wp[usize] = cy;
0124         wsize = usize + cy;
0125         if (usign)
0126             wsign = 1;
0127     }
0128
0129     w->nlimbs = wsize;
0130     w->sign = wsign;
0131 }
0132 EXPORT_SYMBOL_GPL(mpi_add);
0133
0134 void mpi_sub(MPI w, MPI u, MPI v)
0135 {
0136     MPI vv = mpi_copy(v);
0137     vv->sign = !vv->sign;
0138     mpi_add(w, u, vv);
0139     mpi_free(vv);
0140 }
0141 EXPORT_SYMBOL_GPL(mpi_sub);
0142
0143 void mpi_addm(MPI w, MPI u, MPI v, MPI m)
0144 {
0145     mpi_add(w, u, v);
0146     mpi_mod(w, w, m);
0147 }
0148 EXPORT_SYMBOL_GPL(mpi_addm);
0149
0150 void mpi_subm(MPI w, MPI u, MPI v, MPI m)
0151 {
0152     mpi_sub(w, u, v);
0153     mpi_mod(w, w, m);
0154 }
0155 EXPORT_SYMBOL_GPL(mpi_subm);