raw
mpi-genesis             1 /* mpi-add.c  -  MPI functions
mpi_second_cut          2  * Modified by No Such Labs. (C) 2015. See README.
mpi-genesis             3  *
mpi_second_cut          4  * This file was originally part of Gnu Privacy Guard (GPG), ver. 1.4.10,
mpi_second_cut          5  * SHA256(gnupg-1.4.10.tar.gz):
mpi_second_cut          6  *        0bfd74660a2f6cedcf7d8256db4a63c996ffebbcdc2cf54397bfb72878c5a85a
mpi_second_cut          7  * (C) 1994-2005 Free Software Foundation, Inc.
mpi-genesis             8  *
mpi_second_cut          9  * This program is free software: you can redistribute it and/or modify
mpi-genesis            10  * it under the terms of the GNU General Public License as published by
mpi_second_cut         11  * the Free Software Foundation, either version 3 of the License, or
mpi-genesis            12  * (at your option) any later version.
mpi-genesis            13  *
mpi_second_cut         14  * This program is distributed in the hope that it will be useful,
mpi-genesis            15  * but WITHOUT ANY WARRANTY; without even the implied warranty of
mpi-genesis            16  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
mpi-genesis            17  * GNU General Public License for more details.
mpi-genesis            18  *
mpi-genesis            19  * You should have received a copy of the GNU General Public License
mpi_second_cut         20  * along with this program.  If not, see <http://www.gnu.org/licenses/>.
mpi-genesis            21  */
mpi-genesis            22 
mpi-genesis            23 #include <stdio.h>
mpi-genesis            24 #include <stdlib.h>
mpi-genesis            25 
mpi_second_cut         26 #include "knobs.h"
mpi-genesis            27 #include "mpi-internal.h"
mpi-genesis            28 
mpi-genesis            29 
mpi-genesis            30 /****************
mpi-genesis            31  * Add the unsigned integer V to the mpi-integer U and store the
mpi-genesis            32  * result in W. U and V may be the same.
mpi-genesis            33  */
mpi-genesis            34 void
mpi-genesis            35 mpi_add_ui(MPI w, MPI u, unsigned long v )
mpi-genesis            36 {
mpi-genesis            37     mpi_ptr_t wp, up;
mpi-genesis            38     mpi_size_t usize, wsize;
mpi-genesis            39     int usign, wsign;
mpi-genesis            40 
mpi-genesis            41     usize = u->nlimbs;
mpi-genesis            42     usign = u->sign;
mpi-genesis            43     wsign = 0;
mpi-genesis            44 
mpi-genesis            45     /* If not space for W (and possible carry), increase space.  */
mpi-genesis            46     wsize = usize + 1;
mpi-genesis            47     if( w->alloced < wsize )
mpi-genesis            48 	mpi_resize(w, wsize);
mpi-genesis            49 
mpi-genesis            50     /* These must be after realloc (U may be the same as W).  */
mpi-genesis            51     up = u->d;
mpi-genesis            52     wp = w->d;
mpi-genesis            53 
mpi-genesis            54     if( !usize ) {  /* simple */
mpi-genesis            55 	wp[0] = v;
mpi-genesis            56 	wsize = v? 1:0;
mpi-genesis            57     }
mpi-genesis            58     else if( !usign ) {  /* mpi is not negative */
mpi-genesis            59 	mpi_limb_t cy;
mpi-genesis            60 	cy = mpihelp_add_1(wp, up, usize, v);
mpi-genesis            61 	wp[usize] = cy;
mpi-genesis            62 	wsize = usize + cy;
mpi-genesis            63     }
mpi-genesis            64     else {  /* The signs are different.  Need exact comparison to determine
mpi-genesis            65 	     * which operand to subtract from which.  */
mpi-genesis            66 	if( usize == 1 && up[0] < v ) {
mpi-genesis            67 	    wp[0] = v - up[0];
mpi-genesis            68 	    wsize = 1;
mpi-genesis            69 	}
mpi-genesis            70 	else {
mpi-genesis            71 	    mpihelp_sub_1(wp, up, usize, v);
mpi-genesis            72 	    /* Size can decrease with at most one limb. */
mpi-genesis            73 	    wsize = usize - (wp[usize-1]==0);
mpi-genesis            74 	    wsign = 1;
mpi-genesis            75 	}
mpi-genesis            76     }
mpi-genesis            77 
mpi-genesis            78     w->nlimbs = wsize;
mpi-genesis            79     w->sign   = wsign;
mpi-genesis            80 }
mpi-genesis            81 
mpi-genesis            82 
mpi-genesis            83 void
mpi-genesis            84 mpi_add(MPI w, MPI u, MPI v)
mpi-genesis            85 {
mpi-genesis            86     mpi_ptr_t wp, up, vp;
mpi-genesis            87     mpi_size_t usize, vsize, wsize;
mpi-genesis            88     int usign, vsign, wsign;
mpi-genesis            89 
mpi-genesis            90     if( u->nlimbs < v->nlimbs ) { /* Swap U and V. */
mpi-genesis            91 	usize = v->nlimbs;
mpi-genesis            92 	usign = v->sign;
mpi-genesis            93 	vsize = u->nlimbs;
mpi-genesis            94 	vsign = u->sign;
mpi-genesis            95 	wsize = usize + 1;
mpi-genesis            96 	RESIZE_IF_NEEDED(w, wsize);
mpi-genesis            97 	/* These must be after realloc (u or v may be the same as w).  */
mpi-genesis            98 	up    = v->d;
mpi-genesis            99 	vp    = u->d;
mpi-genesis           100     }
mpi-genesis           101     else {
mpi-genesis           102 	usize = u->nlimbs;
mpi-genesis           103 	usign = u->sign;
mpi-genesis           104 	vsize = v->nlimbs;
mpi-genesis           105 	vsign = v->sign;
mpi-genesis           106 	wsize = usize + 1;
mpi-genesis           107 	RESIZE_IF_NEEDED(w, wsize);
mpi-genesis           108 	/* These must be after realloc (u or v may be the same as w).  */
mpi-genesis           109 	up    = u->d;
mpi-genesis           110 	vp    = v->d;
mpi-genesis           111     }
mpi-genesis           112     wp = w->d;
mpi-genesis           113     wsign = 0;
mpi-genesis           114 
mpi-genesis           115     if( !vsize ) {  /* simple */
mpi-genesis           116 	MPN_COPY(wp, up, usize );
mpi-genesis           117 	wsize = usize;
mpi-genesis           118 	wsign = usign;
mpi-genesis           119     }
mpi-genesis           120     else if( usign != vsign ) { /* different sign */
mpi-genesis           121 	/* This test is right since USIZE >= VSIZE */
mpi-genesis           122 	if( usize != vsize ) {
mpi-genesis           123 	    mpihelp_sub(wp, up, usize, vp, vsize);
mpi-genesis           124 	    wsize = usize;
mpi-genesis           125 	    MPN_NORMALIZE(wp, wsize);
mpi-genesis           126 	    wsign = usign;
mpi-genesis           127 	}
mpi-genesis           128 	else if( mpihelp_cmp(up, vp, usize) < 0 ) {
mpi-genesis           129 	    mpihelp_sub_n(wp, vp, up, usize);
mpi-genesis           130 	    wsize = usize;
mpi-genesis           131 	    MPN_NORMALIZE(wp, wsize);
mpi-genesis           132 	    if( !usign )
mpi-genesis           133 		wsign = 1;
mpi-genesis           134 	}
mpi-genesis           135 	else {
mpi-genesis           136 	    mpihelp_sub_n(wp, up, vp, usize);
mpi-genesis           137 	    wsize = usize;
mpi-genesis           138 	    MPN_NORMALIZE(wp, wsize);
mpi-genesis           139 	    if( usign )
mpi-genesis           140 		wsign = 1;
mpi-genesis           141 	}
mpi-genesis           142     }
mpi-genesis           143     else { /* U and V have same sign. Add them. */
mpi-genesis           144 	mpi_limb_t cy = mpihelp_add(wp, up, usize, vp, vsize);
mpi-genesis           145 	wp[usize] = cy;
mpi-genesis           146 	wsize = usize + cy;
mpi-genesis           147 	if( usign )
mpi-genesis           148 	    wsign = 1;
mpi-genesis           149     }
mpi-genesis           150 
mpi-genesis           151     w->nlimbs = wsize;
mpi-genesis           152     w->sign = wsign;
mpi-genesis           153 }
mpi-genesis           154 
mpi-genesis           155 
mpi-genesis           156 /****************
mpi-genesis           157  * Subtract the unsigned integer V from the mpi-integer U and store the
mpi-genesis           158  * result in W.
mpi-genesis           159  */
mpi-genesis           160 void
mpi-genesis           161 mpi_sub_ui(MPI w, MPI u, unsigned long v )
mpi-genesis           162 {
mpi-genesis           163     mpi_ptr_t wp, up;
mpi-genesis           164     mpi_size_t usize, wsize;
mpi-genesis           165     int usign, wsign;
mpi-genesis           166 
mpi-genesis           167     usize = u->nlimbs;
mpi-genesis           168     usign = u->sign;
mpi-genesis           169     wsign = 0;
mpi-genesis           170 
mpi-genesis           171     /* If not space for W (and possible carry), increase space.  */
mpi-genesis           172     wsize = usize + 1;
mpi-genesis           173     if( w->alloced < wsize )
mpi-genesis           174 	mpi_resize(w, wsize);
mpi-genesis           175 
mpi-genesis           176     /* These must be after realloc (U may be the same as W).  */
mpi-genesis           177     up = u->d;
mpi-genesis           178     wp = w->d;
mpi-genesis           179 
mpi-genesis           180     if( !usize ) {  /* simple */
mpi-genesis           181 	wp[0] = v;
mpi-genesis           182 	wsize = v? 1:0;
mpi-genesis           183 	wsign = 1;
mpi-genesis           184     }
mpi-genesis           185     else if( usign ) {	/* mpi and v are negative */
mpi-genesis           186 	mpi_limb_t cy;
mpi-genesis           187 	cy = mpihelp_add_1(wp, up, usize, v);
mpi-genesis           188 	wp[usize] = cy;
mpi-genesis           189 	wsize = usize + cy;
mpi-genesis           190     }
mpi-genesis           191     else {  /* The signs are different.  Need exact comparison to determine
mpi-genesis           192 	     * which operand to subtract from which.  */
mpi-genesis           193 	if( usize == 1 && up[0] < v ) {
mpi-genesis           194 	    wp[0] = v - up[0];
mpi-genesis           195 	    wsize = 1;
mpi-genesis           196 	    wsign = 1;
mpi-genesis           197 	}
mpi-genesis           198 	else {
mpi-genesis           199 	    mpihelp_sub_1(wp, up, usize, v);
mpi-genesis           200 	    /* Size can decrease with at most one limb. */
mpi-genesis           201 	    wsize = usize - (wp[usize-1]==0);
mpi-genesis           202 	}
mpi-genesis           203     }
mpi-genesis           204 
mpi-genesis           205     w->nlimbs = wsize;
mpi-genesis           206     w->sign   = wsign;
mpi-genesis           207 }
mpi-genesis           208 
mpi-genesis           209 void
mpi-genesis           210 mpi_sub(MPI w, MPI u, MPI v)
mpi-genesis           211 {
mpi-genesis           212     if( w == v ) {
mpi-genesis           213 	MPI vv = mpi_copy(v);
mpi-genesis           214 	vv->sign = !vv->sign;
mpi-genesis           215 	mpi_add( w, u, vv );
mpi-genesis           216 	mpi_free(vv);
mpi-genesis           217     }
mpi-genesis           218     else {
mpi-genesis           219 	/* fixme: this is not thread-save (we temp. modify v) */
mpi-genesis           220 	v->sign = !v->sign;
mpi-genesis           221 	mpi_add( w, u, v );
mpi-genesis           222 	v->sign = !v->sign;
mpi-genesis           223     }
mpi-genesis           224 }
mpi-genesis           225 
mpi-genesis           226 
mpi-genesis           227 void
mpi-genesis           228 mpi_addm( MPI w, MPI u, MPI v, MPI m)
mpi-genesis           229 {
mpi-genesis           230     mpi_add(w, u, v);
mpi-genesis           231     mpi_fdiv_r( w, w, m );
mpi-genesis           232 }
mpi-genesis           233 
mpi-genesis           234 void
mpi-genesis           235 mpi_subm( MPI w, MPI u, MPI v, MPI m)
mpi-genesis           236 {
mpi-genesis           237     mpi_sub(w, u, v);
mpi-genesis           238     mpi_fdiv_r( w, w, m );
mpi-genesis           239 }
mpi-genesis           240