1/* mpi-add.c - MPI functions 2 * Copyright (C) 1994, 1996, 1998, 2001, 2002, 2003 Free Software Foundation, Inc. 3 * 4 * This file is part of Libgcrypt. 5 * 6 * Libgcrypt is free software; you can redistribute it and/or modify 7 * it under the terms of the GNU Lesser General Public License as 8 * published by the Free Software Foundation; either version 2.1 of 9 * the License, or (at your option) any later version. 10 * 11 * Libgcrypt is distributed in the hope that it will be useful, 12 * but WITHOUT ANY WARRANTY; without even the implied warranty of 13 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 14 * GNU Lesser General Public License for more details. 15 * 16 * You should have received a copy of the GNU Lesser General Public 17 * License along with this program; if not, write to the Free Software 18 * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA 19 * 20 * Note: This code is heavily based on the GNU MP Library. 21 * Actually it's the same code with only minor changes in the 22 * way the data is stored; this is to support the abstraction 23 * of an optional secure memory allocation which may be used 24 * to avoid revealing of sensitive data due to paging etc. 25 */ 26 27#include <config.h> 28#include <stdio.h> 29#include <stdlib.h> 30 31#include "mpi-internal.h" 32 33 34/**************** 35 * Add the unsigned integer V to the mpi-integer U and store the 36 * result in W. U and V may be the same. 37 */ 38void 39gcry_mpi_add_ui(gcry_mpi_t w, gcry_mpi_t u, unsigned long v ) 40{ 41 mpi_ptr_t wp, up; 42 mpi_size_t usize, wsize; 43 int usign, wsign; 44 45 usize = u->nlimbs; 46 usign = u->sign; 47 wsign = 0; 48 49 /* If not space for W (and possible carry), increase space. */ 50 wsize = usize + 1; 51 if( w->alloced < wsize ) 52 mpi_resize(w, wsize); 53 54 /* These must be after realloc (U may be the same as W). */ 55 up = u->d; 56 wp = w->d; 57 58 if( !usize ) { /* simple */ 59 wp[0] = v; 60 wsize = v? 1:0; 61 } 62 else if( !usign ) { /* mpi is not negative */ 63 mpi_limb_t cy; 64 cy = _gcry_mpih_add_1(wp, up, usize, v); 65 wp[usize] = cy; 66 wsize = usize + cy; 67 } 68 else { /* The signs are different. Need exact comparison to determine 69 * which operand to subtract from which. */ 70 if( usize == 1 && up[0] < v ) { 71 wp[0] = v - up[0]; 72 wsize = 1; 73 } 74 else { 75 _gcry_mpih_sub_1(wp, up, usize, v); 76 /* Size can decrease with at most one limb. */ 77 wsize = usize - (wp[usize-1]==0); 78 wsign = 1; 79 } 80 } 81 82 w->nlimbs = wsize; 83 w->sign = wsign; 84} 85 86 87void 88gcry_mpi_add(gcry_mpi_t w, gcry_mpi_t u, gcry_mpi_t 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 RESIZE_IF_NEEDED(w, wsize); 101 /* These must be after realloc (u or v may be the same as w). */ 102 up = v->d; 103 vp = u->d; 104 } 105 else { 106 usize = u->nlimbs; 107 usign = u->sign; 108 vsize = v->nlimbs; 109 vsign = v->sign; 110 wsize = usize + 1; 111 RESIZE_IF_NEEDED(w, wsize); 112 /* These must be after realloc (u or v may be the same as w). */ 113 up = u->d; 114 vp = v->d; 115 } 116 wp = w->d; 117 wsign = 0; 118 119 if( !vsize ) { /* simple */ 120 MPN_COPY(wp, up, usize ); 121 wsize = usize; 122 wsign = usign; 123 } 124 else if( usign != vsign ) { /* different sign */ 125 /* This test is right since USIZE >= VSIZE */ 126 if( usize != vsize ) { 127 _gcry_mpih_sub(wp, up, usize, vp, vsize); 128 wsize = usize; 129 MPN_NORMALIZE(wp, wsize); 130 wsign = usign; 131 } 132 else if( _gcry_mpih_cmp(up, vp, usize) < 0 ) { 133 _gcry_mpih_sub_n(wp, vp, up, usize); 134 wsize = usize; 135 MPN_NORMALIZE(wp, wsize); 136 if( !usign ) 137 wsign = 1; 138 } 139 else { 140 _gcry_mpih_sub_n(wp, up, vp, usize); 141 wsize = usize; 142 MPN_NORMALIZE(wp, wsize); 143 if( usign ) 144 wsign = 1; 145 } 146 } 147 else { /* U and V have same sign. Add them. */ 148 mpi_limb_t cy = _gcry_mpih_add(wp, up, usize, vp, vsize); 149 wp[usize] = cy; 150 wsize = usize + cy; 151 if( usign ) 152 wsign = 1; 153 } 154 155 w->nlimbs = wsize; 156 w->sign = wsign; 157} 158 159 160/**************** 161 * Subtract the unsigned integer V from the mpi-integer U and store the 162 * result in W. 163 */ 164void 165gcry_mpi_sub_ui(gcry_mpi_t w, gcry_mpi_t u, unsigned long v ) 166{ 167 mpi_ptr_t wp, up; 168 mpi_size_t usize, wsize; 169 int usign, wsign; 170 171 usize = u->nlimbs; 172 usign = u->sign; 173 wsign = 0; 174 175 /* If not space for W (and possible carry), increase space. */ 176 wsize = usize + 1; 177 if( w->alloced < wsize ) 178 mpi_resize(w, wsize); 179 180 /* These must be after realloc (U may be the same as W). */ 181 up = u->d; 182 wp = w->d; 183 184 if( !usize ) { /* simple */ 185 wp[0] = v; 186 wsize = v? 1:0; 187 wsign = 1; 188 } 189 else if( usign ) { /* mpi and v are negative */ 190 mpi_limb_t cy; 191 cy = _gcry_mpih_add_1(wp, up, usize, v); 192 wp[usize] = cy; 193 wsize = usize + cy; 194 } 195 else { /* The signs are different. Need exact comparison to determine 196 * which operand to subtract from which. */ 197 if( usize == 1 && up[0] < v ) { 198 wp[0] = v - up[0]; 199 wsize = 1; 200 wsign = 1; 201 } 202 else { 203 _gcry_mpih_sub_1(wp, up, usize, v); 204 /* Size can decrease with at most one limb. */ 205 wsize = usize - (wp[usize-1]==0); 206 } 207 } 208 209 w->nlimbs = wsize; 210 w->sign = wsign; 211} 212 213void 214gcry_mpi_sub(gcry_mpi_t w, gcry_mpi_t u, gcry_mpi_t v) 215{ 216 gcry_mpi_t vv = mpi_copy (v); 217 vv->sign = ! vv->sign; 218 gcry_mpi_add (w, u, vv); 219 mpi_free (vv); 220} 221 222 223void 224gcry_mpi_addm( gcry_mpi_t w, gcry_mpi_t u, gcry_mpi_t v, gcry_mpi_t m) 225{ 226 gcry_mpi_add(w, u, v); 227 _gcry_mpi_fdiv_r( w, w, m ); 228} 229 230void 231gcry_mpi_subm( gcry_mpi_t w, gcry_mpi_t u, gcry_mpi_t v, gcry_mpi_t m) 232{ 233 gcry_mpi_sub(w, u, v); 234 _gcry_mpi_fdiv_r( w, w, m ); 235} 236