1/* mpi-div.c - MPI functions 2 * Copyright (C) 1994, 1996, 1998, 2001, 2002, 3 * 2003 Free Software Foundation, Inc. 4 * 5 * This file is part of Libgcrypt. 6 * 7 * Libgcrypt is free software; you can redistribute it and/or modify 8 * it under the terms of the GNU Lesser General Public License as 9 * published by the Free Software Foundation; either version 2.1 of 10 * the License, or (at your option) any later version. 11 * 12 * Libgcrypt 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 Lesser General Public License for more details. 16 * 17 * You should have received a copy of the GNU Lesser General Public 18 * License 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 */ 27 28#include <config.h> 29#include <stdio.h> 30#include <stdlib.h> 31#include "mpi-internal.h" 32#include "longlong.h" 33#include "g10lib.h" 34 35 36void 37_gcry_mpi_fdiv_r( gcry_mpi_t rem, gcry_mpi_t dividend, gcry_mpi_t divisor ) 38{ 39 int divisor_sign = divisor->sign; 40 gcry_mpi_t temp_divisor = NULL; 41 42 /* We need the original value of the divisor after the remainder has been 43 * preliminary calculated. We have to copy it to temporary space if it's 44 * the same variable as REM. */ 45 if( rem == divisor ) { 46 temp_divisor = mpi_copy( divisor ); 47 divisor = temp_divisor; 48 } 49 50 _gcry_mpi_tdiv_r( rem, dividend, divisor ); 51 52 if( ((divisor_sign?1:0) ^ (dividend->sign?1:0)) && rem->nlimbs ) 53 gcry_mpi_add( rem, rem, divisor); 54 55 if( temp_divisor ) 56 mpi_free(temp_divisor); 57} 58 59 60 61/**************** 62 * Division rounding the quotient towards -infinity. 63 * The remainder gets the same sign as the denominator. 64 * rem is optional 65 */ 66 67ulong 68_gcry_mpi_fdiv_r_ui( gcry_mpi_t rem, gcry_mpi_t dividend, ulong divisor ) 69{ 70 mpi_limb_t rlimb; 71 72 rlimb = _gcry_mpih_mod_1( dividend->d, dividend->nlimbs, divisor ); 73 if( rlimb && dividend->sign ) 74 rlimb = divisor - rlimb; 75 76 if( rem ) { 77 rem->d[0] = rlimb; 78 rem->nlimbs = rlimb? 1:0; 79 } 80 return rlimb; 81} 82 83 84void 85_gcry_mpi_fdiv_q( gcry_mpi_t quot, gcry_mpi_t dividend, gcry_mpi_t divisor ) 86{ 87 gcry_mpi_t tmp = mpi_alloc( mpi_get_nlimbs(quot) ); 88 _gcry_mpi_fdiv_qr( quot, tmp, dividend, divisor); 89 mpi_free(tmp); 90} 91 92void 93_gcry_mpi_fdiv_qr( gcry_mpi_t quot, gcry_mpi_t rem, gcry_mpi_t dividend, gcry_mpi_t divisor ) 94{ 95 int divisor_sign = divisor->sign; 96 gcry_mpi_t temp_divisor = NULL; 97 98 if( quot == divisor || rem == divisor ) { 99 temp_divisor = mpi_copy( divisor ); 100 divisor = temp_divisor; 101 } 102 103 _gcry_mpi_tdiv_qr( quot, rem, dividend, divisor ); 104 105 if( (divisor_sign ^ dividend->sign) && rem->nlimbs ) { 106 gcry_mpi_sub_ui( quot, quot, 1 ); 107 gcry_mpi_add( rem, rem, divisor); 108 } 109 110 if( temp_divisor ) 111 mpi_free(temp_divisor); 112} 113 114 115/* If den == quot, den needs temporary storage. 116 * If den == rem, den needs temporary storage. 117 * If num == quot, num needs temporary storage. 118 * If den has temporary storage, it can be normalized while being copied, 119 * i.e no extra storage should be allocated. 120 */ 121 122void 123_gcry_mpi_tdiv_r( gcry_mpi_t rem, gcry_mpi_t num, gcry_mpi_t den) 124{ 125 _gcry_mpi_tdiv_qr(NULL, rem, num, den ); 126} 127 128void 129_gcry_mpi_tdiv_qr( gcry_mpi_t quot, gcry_mpi_t rem, gcry_mpi_t num, gcry_mpi_t den) 130{ 131 mpi_ptr_t np, dp; 132 mpi_ptr_t qp, rp; 133 mpi_size_t nsize = num->nlimbs; 134 mpi_size_t dsize = den->nlimbs; 135 mpi_size_t qsize, rsize; 136 mpi_size_t sign_remainder = num->sign; 137 mpi_size_t sign_quotient = num->sign ^ den->sign; 138 unsigned normalization_steps; 139 mpi_limb_t q_limb; 140 mpi_ptr_t marker[5]; 141 unsigned int marker_nlimbs[5]; 142 int markidx=0; 143 144 /* Ensure space is enough for quotient and remainder. 145 * We need space for an extra limb in the remainder, because it's 146 * up-shifted (normalized) below. */ 147 rsize = nsize + 1; 148 mpi_resize( rem, rsize); 149 150 qsize = rsize - dsize; /* qsize cannot be bigger than this. */ 151 if( qsize <= 0 ) { 152 if( num != rem ) { 153 rem->nlimbs = num->nlimbs; 154 rem->sign = num->sign; 155 MPN_COPY(rem->d, num->d, nsize); 156 } 157 if( quot ) { 158 /* This needs to follow the assignment to rem, in case the 159 * numerator and quotient are the same. */ 160 quot->nlimbs = 0; 161 quot->sign = 0; 162 } 163 return; 164 } 165 166 if( quot ) 167 mpi_resize( quot, qsize); 168 169 /* Read pointers here, when reallocation is finished. */ 170 np = num->d; 171 dp = den->d; 172 rp = rem->d; 173 174 /* Optimize division by a single-limb divisor. */ 175 if( dsize == 1 ) { 176 mpi_limb_t rlimb; 177 if( quot ) { 178 qp = quot->d; 179 rlimb = _gcry_mpih_divmod_1( qp, np, nsize, dp[0] ); 180 qsize -= qp[qsize - 1] == 0; 181 quot->nlimbs = qsize; 182 quot->sign = sign_quotient; 183 } 184 else 185 rlimb = _gcry_mpih_mod_1( np, nsize, dp[0] ); 186 rp[0] = rlimb; 187 rsize = rlimb != 0?1:0; 188 rem->nlimbs = rsize; 189 rem->sign = sign_remainder; 190 return; 191 } 192 193 194 if( quot ) { 195 qp = quot->d; 196 /* Make sure QP and NP point to different objects. Otherwise the 197 * numerator would be gradually overwritten by the quotient limbs. */ 198 if(qp == np) { /* Copy NP object to temporary space. */ 199 marker_nlimbs[markidx] = nsize; 200 np = marker[markidx++] = mpi_alloc_limb_space(nsize, 201 mpi_is_secure(quot)); 202 MPN_COPY(np, qp, nsize); 203 } 204 } 205 else /* Put quotient at top of remainder. */ 206 qp = rp + dsize; 207 208 count_leading_zeros( normalization_steps, dp[dsize - 1] ); 209 210 /* Normalize the denominator, i.e. make its most significant bit set by 211 * shifting it NORMALIZATION_STEPS bits to the left. Also shift the 212 * numerator the same number of steps (to keep the quotient the same!). 213 */ 214 if( normalization_steps ) { 215 mpi_ptr_t tp; 216 mpi_limb_t nlimb; 217 218 /* Shift up the denominator setting the most significant bit of 219 * the most significant word. Use temporary storage not to clobber 220 * the original contents of the denominator. */ 221 marker_nlimbs[markidx] = dsize; 222 tp = marker[markidx++] = mpi_alloc_limb_space(dsize,mpi_is_secure(den)); 223 _gcry_mpih_lshift( tp, dp, dsize, normalization_steps ); 224 dp = tp; 225 226 /* Shift up the numerator, possibly introducing a new most 227 * significant word. Move the shifted numerator in the remainder 228 * meanwhile. */ 229 nlimb = _gcry_mpih_lshift(rp, np, nsize, normalization_steps); 230 if( nlimb ) { 231 rp[nsize] = nlimb; 232 rsize = nsize + 1; 233 } 234 else 235 rsize = nsize; 236 } 237 else { 238 /* The denominator is already normalized, as required. Copy it to 239 * temporary space if it overlaps with the quotient or remainder. */ 240 if( dp == rp || (quot && (dp == qp))) { 241 mpi_ptr_t tp; 242 243 marker_nlimbs[markidx] = dsize; 244 tp = marker[markidx++] = mpi_alloc_limb_space(dsize, 245 mpi_is_secure(den)); 246 MPN_COPY( tp, dp, dsize ); 247 dp = tp; 248 } 249 250 /* Move the numerator to the remainder. */ 251 if( rp != np ) 252 MPN_COPY(rp, np, nsize); 253 254 rsize = nsize; 255 } 256 257 q_limb = _gcry_mpih_divrem( qp, 0, rp, rsize, dp, dsize ); 258 259 if( quot ) { 260 qsize = rsize - dsize; 261 if(q_limb) { 262 qp[qsize] = q_limb; 263 qsize += 1; 264 } 265 266 quot->nlimbs = qsize; 267 quot->sign = sign_quotient; 268 } 269 270 rsize = dsize; 271 MPN_NORMALIZE (rp, rsize); 272 273 if( normalization_steps && rsize ) { 274 _gcry_mpih_rshift(rp, rp, rsize, normalization_steps); 275 rsize -= rp[rsize - 1] == 0?1:0; 276 } 277 278 rem->nlimbs = rsize; 279 rem->sign = sign_remainder; 280 while( markidx ) 281 { 282 markidx--; 283 _gcry_mpi_free_limb_space (marker[markidx], marker_nlimbs[markidx]); 284 } 285} 286 287void 288_gcry_mpi_tdiv_q_2exp( gcry_mpi_t w, gcry_mpi_t u, unsigned int count ) 289{ 290 mpi_size_t usize, wsize; 291 mpi_size_t limb_cnt; 292 293 usize = u->nlimbs; 294 limb_cnt = count / BITS_PER_MPI_LIMB; 295 wsize = usize - limb_cnt; 296 if( limb_cnt >= usize ) 297 w->nlimbs = 0; 298 else { 299 mpi_ptr_t wp; 300 mpi_ptr_t up; 301 302 RESIZE_IF_NEEDED( w, wsize ); 303 wp = w->d; 304 up = u->d; 305 306 count %= BITS_PER_MPI_LIMB; 307 if( count ) { 308 _gcry_mpih_rshift( wp, up + limb_cnt, wsize, count ); 309 wsize -= !wp[wsize - 1]; 310 } 311 else { 312 MPN_COPY_INCR( wp, up + limb_cnt, wsize); 313 } 314 315 w->nlimbs = wsize; 316 } 317} 318 319/**************** 320 * Check whether dividend is divisible by divisor 321 * (note: divisor must fit into a limb) 322 */ 323int 324_gcry_mpi_divisible_ui(gcry_mpi_t dividend, ulong divisor ) 325{ 326 return !_gcry_mpih_mod_1( dividend->d, dividend->nlimbs, divisor ); 327} 328 329 330void 331gcry_mpi_div (gcry_mpi_t quot, gcry_mpi_t rem, gcry_mpi_t dividend, gcry_mpi_t divisor, int round) 332{ 333 if (!round) 334 { 335 if (!rem) 336 { 337 gcry_mpi_t tmp = mpi_alloc (mpi_get_nlimbs(quot)); 338 _gcry_mpi_tdiv_qr (quot, tmp, dividend, divisor); 339 mpi_free (tmp); 340 } 341 else 342 _gcry_mpi_tdiv_qr (quot, rem, dividend, divisor); 343 } 344 else if (round < 0) 345 { 346 if (!rem) 347 _gcry_mpi_fdiv_q (quot, dividend, divisor); 348 else if (!quot) 349 _gcry_mpi_fdiv_r (rem, dividend, divisor); 350 else 351 _gcry_mpi_fdiv_qr (quot, rem, dividend, divisor); 352 } 353 else 354 log_bug ("mpi rounding to ceiling not yet implemented\n"); 355} 356