mpi-genesis 1
mpi-genesis 2 * Copyright (C) 1994, 1996 Free Software Foundation, Inc.
mpi-genesis 3 * Copyright (C) 1998, 2001 Free Software Foundation, Inc.
mpi-genesis 4 *
mpi-genesis 5 * This file is part of GnuPG.
mpi-genesis 6 *
mpi-genesis 7 * GnuPG is free software; you can redistribute it and/or modify
mpi-genesis 8 * it under the terms of the GNU General Public License as published by
mpi-genesis 9 * the Free Software Foundation; either version 3 of the License, or
mpi-genesis 10 * (at your option) any later version.
mpi-genesis 11 *
mpi-genesis 12 * GnuPG is distributed in the hope that it will be useful,
mpi-genesis 13 * but WITHOUT ANY WARRANTY; without even the implied warranty of
mpi-genesis 14 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
mpi-genesis 15 * GNU General Public License for more details.
mpi-genesis 16 *
mpi-genesis 17 * You should have received a copy of the GNU General Public License
mpi-genesis 18 * along with this program; if not, see <http:
mpi-genesis 19 *
mpi-genesis 20 * Note: This code is heavily based on the GNU MP Library.
mpi-genesis 21 * Actually it's the same code with only minor changes in the
mpi-genesis 22 * way the data is stored; this is to support the abstraction
mpi-genesis 23 * of an optional secure memory allocation which may be used
mpi-genesis 24 * to avoid revealing of sensitive data due to paging etc.
mpi-genesis 25 * The GNU MP Library itself is published under the LGPL;
mpi-genesis 26 * however I decided to publish this code under the plain GPL.
mpi-genesis 27 */
mpi-genesis 28
mpi-genesis 29 #include <config.h>
mpi-genesis 30 #include <stdio.h>
mpi-genesis 31 #include <stdlib.h>
mpi-genesis 32 #include "mpi-internal.h"
mpi-genesis 33
mpi-genesis 34
mpi-genesis 35 void
mpi-genesis 36 mpi_mul_ui( MPI prod, MPI mult, unsigned long small_mult )
mpi-genesis 37 {
mpi-genesis 38 mpi_size_t size, prod_size;
mpi-genesis 39 mpi_ptr_t prod_ptr;
mpi-genesis 40 mpi_limb_t cy;
mpi-genesis 41 int sign;
mpi-genesis 42
mpi-genesis 43 size = mult->nlimbs;
mpi-genesis 44 sign = mult->sign;
mpi-genesis 45
mpi-genesis 46 if( !size || !small_mult ) {
mpi-genesis 47 prod->nlimbs = 0;
mpi-genesis 48 prod->sign = 0;
mpi-genesis 49 return;
mpi-genesis 50 }
mpi-genesis 51
mpi-genesis 52 prod_size = size + 1;
mpi-genesis 53 if( prod->alloced < prod_size )
mpi-genesis 54 mpi_resize( prod, prod_size );
mpi-genesis 55 prod_ptr = prod->d;
mpi-genesis 56
mpi-genesis 57 cy = mpihelp_mul_1( prod_ptr, mult->d, size, (mpi_limb_t)small_mult );
mpi-genesis 58 if( cy )
mpi-genesis 59 prod_ptr[size++] = cy;
mpi-genesis 60 prod->nlimbs = size;
mpi-genesis 61 prod->sign = sign;
mpi-genesis 62 }
mpi-genesis 63
mpi-genesis 64
mpi-genesis 65 void
mpi-genesis 66 mpi_mul_2exp( MPI w, MPI u, unsigned long cnt)
mpi-genesis 67 {
mpi-genesis 68 mpi_size_t usize, wsize, limb_cnt;
mpi-genesis 69 mpi_ptr_t wp;
mpi-genesis 70 mpi_limb_t wlimb;
mpi-genesis 71 int usign, wsign;
mpi-genesis 72
mpi-genesis 73 usize = u->nlimbs;
mpi-genesis 74 usign = u->sign;
mpi-genesis 75
mpi-genesis 76 if( !usize ) {
mpi-genesis 77 w->nlimbs = 0;
mpi-genesis 78 w->sign = 0;
mpi-genesis 79 return;
mpi-genesis 80 }
mpi-genesis 81
mpi-genesis 82 limb_cnt = cnt / BITS_PER_MPI_LIMB;
mpi-genesis 83 wsize = usize + limb_cnt + 1;
mpi-genesis 84 if( w->alloced < wsize )
mpi-genesis 85 mpi_resize(w, wsize );
mpi-genesis 86 wp = w->d;
mpi-genesis 87 wsize = usize + limb_cnt;
mpi-genesis 88 wsign = usign;
mpi-genesis 89
mpi-genesis 90 cnt %= BITS_PER_MPI_LIMB;
mpi-genesis 91 if( cnt ) {
mpi-genesis 92 wlimb = mpihelp_lshift( wp + limb_cnt, u->d, usize, cnt );
mpi-genesis 93 if( wlimb ) {
mpi-genesis 94 wp[wsize] = wlimb;
mpi-genesis 95 wsize++;
mpi-genesis 96 }
mpi-genesis 97 }
mpi-genesis 98 else {
mpi-genesis 99 MPN_COPY_DECR( wp + limb_cnt, u->d, usize );
mpi-genesis 100 }
mpi-genesis 101
mpi-genesis 102
mpi-genesis 103 * mpn_lshift, not to lose for U == W. */
mpi-genesis 104 MPN_ZERO( wp, limb_cnt );
mpi-genesis 105
mpi-genesis 106 w->nlimbs = wsize;
mpi-genesis 107 w->sign = wsign;
mpi-genesis 108 }
mpi-genesis 109
mpi-genesis 110
mpi-genesis 111
mpi-genesis 112 void
mpi-genesis 113 mpi_mul( MPI w, MPI u, MPI v)
mpi-genesis 114 {
mpi-genesis 115 mpi_size_t usize, vsize, wsize;
mpi-genesis 116 mpi_ptr_t up, vp, wp;
mpi-genesis 117 mpi_limb_t cy;
mpi-genesis 118 int usign, vsign, usecure, vsecure, sign_product;
mpi-genesis 119 int assign_wp=0;
mpi-genesis 120 mpi_ptr_t tmp_limb=NULL;
mpi-genesis 121
mpi-genesis 122
mpi-genesis 123 if( u->nlimbs < v->nlimbs ) {
mpi-genesis 124 usize = v->nlimbs;
mpi-genesis 125 usign = v->sign;
mpi-genesis 126 usecure = mpi_is_secure(v);
mpi-genesis 127 up = v->d;
mpi-genesis 128 vsize = u->nlimbs;
mpi-genesis 129 vsign = u->sign;
mpi-genesis 130 vsecure = mpi_is_secure(u);
mpi-genesis 131 vp = u->d;
mpi-genesis 132 }
mpi-genesis 133 else {
mpi-genesis 134 usize = u->nlimbs;
mpi-genesis 135 usign = u->sign;
mpi-genesis 136 usecure = mpi_is_secure(u);
mpi-genesis 137 up = u->d;
mpi-genesis 138 vsize = v->nlimbs;
mpi-genesis 139 vsign = v->sign;
mpi-genesis 140 vsecure = mpi_is_secure(v);
mpi-genesis 141 vp = v->d;
mpi-genesis 142 }
mpi-genesis 143 sign_product = usign ^ vsign;
mpi-genesis 144 wp = w->d;
mpi-genesis 145
mpi-genesis 146
mpi-genesis 147 wsize = usize + vsize;
mpi-genesis 148 if ( !mpi_is_secure (w) && (mpi_is_secure (u) || mpi_is_secure (v)) ) {
mpi-genesis 149
mpi-genesis 150 * that no temporray results are stored in w, we temporary use
mpi-genesis 151 * a newly allocated limb space for w */
mpi-genesis 152 wp = mpi_alloc_limb_space( wsize, 1 );
mpi-genesis 153 assign_wp = 2;
mpi-genesis 154 * mormal memory */
mpi-genesis 155 }
mpi-genesis 156 else if( w->alloced < wsize ) {
mpi-genesis 157 if( wp == up || wp == vp ) {
mpi-genesis 158 wp = mpi_alloc_limb_space( wsize, mpi_is_secure(w) );
mpi-genesis 159 assign_wp = 1;
mpi-genesis 160 }
mpi-genesis 161 else {
mpi-genesis 162 mpi_resize(w, wsize );
mpi-genesis 163 wp = w->d;
mpi-genesis 164 }
mpi-genesis 165 }
mpi-genesis 166 else {
mpi-genesis 167 if( wp == up ) {
mpi-genesis 168
mpi-genesis 169 up = tmp_limb = mpi_alloc_limb_space( usize, usecure );
mpi-genesis 170
mpi-genesis 171 if( wp == vp )
mpi-genesis 172 vp = up;
mpi-genesis 173
mpi-genesis 174 MPN_COPY( up, wp, usize );
mpi-genesis 175 }
mpi-genesis 176 else if( wp == vp ) {
mpi-genesis 177
mpi-genesis 178 vp = tmp_limb = mpi_alloc_limb_space( vsize, vsecure );
mpi-genesis 179
mpi-genesis 180 MPN_COPY( vp, wp, vsize );
mpi-genesis 181 }
mpi-genesis 182 }
mpi-genesis 183
mpi-genesis 184 if( !vsize )
mpi-genesis 185 wsize = 0;
mpi-genesis 186 else {
mpi-genesis 187 cy = mpihelp_mul( wp, up, usize, vp, vsize );
mpi-genesis 188 wsize -= cy? 0:1;
mpi-genesis 189 }
mpi-genesis 190
mpi-genesis 191 if( assign_wp ) {
mpi-genesis 192 if (assign_wp == 2) {
mpi-genesis 193
mpi-genesis 194 mpi_ptr_t tmp_wp = mpi_alloc_limb_space (wsize, 0);
mpi-genesis 195 MPN_COPY (tmp_wp, wp, wsize);
mpi-genesis 196 mpi_free_limb_space (wp);
mpi-genesis 197 wp = tmp_wp;
mpi-genesis 198 }
mpi-genesis 199 mpi_assign_limb_space( w, wp, wsize );
mpi-genesis 200 }
mpi-genesis 201 w->nlimbs = wsize;
mpi-genesis 202 w->sign = sign_product;
mpi-genesis 203 if( tmp_limb )
mpi-genesis 204 mpi_free_limb_space( tmp_limb );
mpi-genesis 205 }
mpi-genesis 206
mpi-genesis 207
mpi-genesis 208 void
mpi-genesis 209 mpi_mulm( MPI w, MPI u, MPI v, MPI m)
mpi-genesis 210 {
mpi-genesis 211 mpi_mul(w, u, v);
mpi-genesis 212 mpi_fdiv_r( w, w, m );
mpi-genesis 213 }
mpi-genesis 214