mpi-genesis~ 1
mpi-genesis~ 2 * Copyright (C) 1998, 1999, 2000, 2001 Free Software Foundation, Inc.
mpi-genesis~ 3 * Copyright (C) 1994, 1996 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
mpi-genesis~ 33 #include "mpi-internal.h"
mpi-genesis~ 34
mpi-genesis~ 35
mpi-genesis~ 36
mpi-genesis~ 37 * Add the unsigned integer V to the mpi-integer U and store the
mpi-genesis~ 38 * result in W. U and V may be the same.
mpi-genesis~ 39 */
mpi-genesis~ 40 void
mpi-genesis~ 41 mpi_add_ui(MPI w, MPI u, unsigned long v )
mpi-genesis~ 42 {
mpi-genesis~ 43 mpi_ptr_t wp, up;
mpi-genesis~ 44 mpi_size_t usize, wsize;
mpi-genesis~ 45 int usign, wsign;
mpi-genesis~ 46
mpi-genesis~ 47 usize = u->nlimbs;
mpi-genesis~ 48 usign = u->sign;
mpi-genesis~ 49 wsign = 0;
mpi-genesis~ 50
mpi-genesis~ 51
mpi-genesis~ 52 wsize = usize + 1;
mpi-genesis~ 53 if( w->alloced < wsize )
mpi-genesis~ 54 mpi_resize(w, wsize);
mpi-genesis~ 55
mpi-genesis~ 56
mpi-genesis~ 57 up = u->d;
mpi-genesis~ 58 wp = w->d;
mpi-genesis~ 59
mpi-genesis~ 60 if( !usize ) {
mpi-genesis~ 61 wp[0] = v;
mpi-genesis~ 62 wsize = v? 1:0;
mpi-genesis~ 63 }
mpi-genesis~ 64 else if( !usign ) {
mpi-genesis~ 65 mpi_limb_t cy;
mpi-genesis~ 66 cy = mpihelp_add_1(wp, up, usize, v);
mpi-genesis~ 67 wp[usize] = cy;
mpi-genesis~ 68 wsize = usize + cy;
mpi-genesis~ 69 }
mpi-genesis~ 70 else {
mpi-genesis~ 71 * which operand to subtract from which. */
mpi-genesis~ 72 if( usize == 1 && up[0] < v ) {
mpi-genesis~ 73 wp[0] = v - up[0];
mpi-genesis~ 74 wsize = 1;
mpi-genesis~ 75 }
mpi-genesis~ 76 else {
mpi-genesis~ 77 mpihelp_sub_1(wp, up, usize, v);
mpi-genesis~ 78
mpi-genesis~ 79 wsize = usize - (wp[usize-1]==0);
mpi-genesis~ 80 wsign = 1;
mpi-genesis~ 81 }
mpi-genesis~ 82 }
mpi-genesis~ 83
mpi-genesis~ 84 w->nlimbs = wsize;
mpi-genesis~ 85 w->sign = wsign;
mpi-genesis~ 86 }
mpi-genesis~ 87
mpi-genesis~ 88
mpi-genesis~ 89 void
mpi-genesis~ 90 mpi_add(MPI w, MPI u, MPI v)
mpi-genesis~ 91 {
mpi-genesis~ 92 mpi_ptr_t wp, up, vp;
mpi-genesis~ 93 mpi_size_t usize, vsize, wsize;
mpi-genesis~ 94 int usign, vsign, wsign;
mpi-genesis~ 95
mpi-genesis~ 96 if( u->nlimbs < v->nlimbs ) {
mpi-genesis~ 97 usize = v->nlimbs;
mpi-genesis~ 98 usign = v->sign;
mpi-genesis~ 99 vsize = u->nlimbs;
mpi-genesis~ 100 vsign = u->sign;
mpi-genesis~ 101 wsize = usize + 1;
mpi-genesis~ 102 RESIZE_IF_NEEDED(w, wsize);
mpi-genesis~ 103
mpi-genesis~ 104 up = v->d;
mpi-genesis~ 105 vp = u->d;
mpi-genesis~ 106 }
mpi-genesis~ 107 else {
mpi-genesis~ 108 usize = u->nlimbs;
mpi-genesis~ 109 usign = u->sign;
mpi-genesis~ 110 vsize = v->nlimbs;
mpi-genesis~ 111 vsign = v->sign;
mpi-genesis~ 112 wsize = usize + 1;
mpi-genesis~ 113 RESIZE_IF_NEEDED(w, wsize);
mpi-genesis~ 114
mpi-genesis~ 115 up = u->d;
mpi-genesis~ 116 vp = v->d;
mpi-genesis~ 117 }
mpi-genesis~ 118 wp = w->d;
mpi-genesis~ 119 wsign = 0;
mpi-genesis~ 120
mpi-genesis~ 121 if( !vsize ) {
mpi-genesis~ 122 MPN_COPY(wp, up, usize );
mpi-genesis~ 123 wsize = usize;
mpi-genesis~ 124 wsign = usign;
mpi-genesis~ 125 }
mpi-genesis~ 126 else if( usign != vsign ) {
mpi-genesis~ 127
mpi-genesis~ 128 if( usize != vsize ) {
mpi-genesis~ 129 mpihelp_sub(wp, up, usize, vp, vsize);
mpi-genesis~ 130 wsize = usize;
mpi-genesis~ 131 MPN_NORMALIZE(wp, wsize);
mpi-genesis~ 132 wsign = usign;
mpi-genesis~ 133 }
mpi-genesis~ 134 else if( mpihelp_cmp(up, vp, usize) < 0 ) {
mpi-genesis~ 135 mpihelp_sub_n(wp, vp, up, usize);
mpi-genesis~ 136 wsize = usize;
mpi-genesis~ 137 MPN_NORMALIZE(wp, wsize);
mpi-genesis~ 138 if( !usign )
mpi-genesis~ 139 wsign = 1;
mpi-genesis~ 140 }
mpi-genesis~ 141 else {
mpi-genesis~ 142 mpihelp_sub_n(wp, up, vp, usize);
mpi-genesis~ 143 wsize = usize;
mpi-genesis~ 144 MPN_NORMALIZE(wp, wsize);
mpi-genesis~ 145 if( usign )
mpi-genesis~ 146 wsign = 1;
mpi-genesis~ 147 }
mpi-genesis~ 148 }
mpi-genesis~ 149 else {
mpi-genesis~ 150 mpi_limb_t cy = mpihelp_add(wp, up, usize, vp, vsize);
mpi-genesis~ 151 wp[usize] = cy;
mpi-genesis~ 152 wsize = usize + cy;
mpi-genesis~ 153 if( usign )
mpi-genesis~ 154 wsign = 1;
mpi-genesis~ 155 }
mpi-genesis~ 156
mpi-genesis~ 157 w->nlimbs = wsize;
mpi-genesis~ 158 w->sign = wsign;
mpi-genesis~ 159 }
mpi-genesis~ 160
mpi-genesis~ 161
mpi-genesis~ 162
mpi-genesis~ 163 * Subtract the unsigned integer V from the mpi-integer U and store the
mpi-genesis~ 164 * result in W.
mpi-genesis~ 165 */
mpi-genesis~ 166 void
mpi-genesis~ 167 mpi_sub_ui(MPI w, MPI u, unsigned long v )
mpi-genesis~ 168 {
mpi-genesis~ 169 mpi_ptr_t wp, up;
mpi-genesis~ 170 mpi_size_t usize, wsize;
mpi-genesis~ 171 int usign, wsign;
mpi-genesis~ 172
mpi-genesis~ 173 usize = u->nlimbs;
mpi-genesis~ 174 usign = u->sign;
mpi-genesis~ 175 wsign = 0;
mpi-genesis~ 176
mpi-genesis~ 177
mpi-genesis~ 178 wsize = usize + 1;
mpi-genesis~ 179 if( w->alloced < wsize )
mpi-genesis~ 180 mpi_resize(w, wsize);
mpi-genesis~ 181
mpi-genesis~ 182
mpi-genesis~ 183 up = u->d;
mpi-genesis~ 184 wp = w->d;
mpi-genesis~ 185
mpi-genesis~ 186 if( !usize ) {
mpi-genesis~ 187 wp[0] = v;
mpi-genesis~ 188 wsize = v? 1:0;
mpi-genesis~ 189 wsign = 1;
mpi-genesis~ 190 }
mpi-genesis~ 191 else if( usign ) {
mpi-genesis~ 192 mpi_limb_t cy;
mpi-genesis~ 193 cy = mpihelp_add_1(wp, up, usize, v);
mpi-genesis~ 194 wp[usize] = cy;
mpi-genesis~ 195 wsize = usize + cy;
mpi-genesis~ 196 }
mpi-genesis~ 197 else {
mpi-genesis~ 198 * which operand to subtract from which. */
mpi-genesis~ 199 if( usize == 1 && up[0] < v ) {
mpi-genesis~ 200 wp[0] = v - up[0];
mpi-genesis~ 201 wsize = 1;
mpi-genesis~ 202 wsign = 1;
mpi-genesis~ 203 }
mpi-genesis~ 204 else {
mpi-genesis~ 205 mpihelp_sub_1(wp, up, usize, v);
mpi-genesis~ 206
mpi-genesis~ 207 wsize = usize - (wp[usize-1]==0);
mpi-genesis~ 208 }
mpi-genesis~ 209 }
mpi-genesis~ 210
mpi-genesis~ 211 w->nlimbs = wsize;
mpi-genesis~ 212 w->sign = wsign;
mpi-genesis~ 213 }
mpi-genesis~ 214
mpi-genesis~ 215 void
mpi-genesis~ 216 mpi_sub(MPI w, MPI u, MPI v)
mpi-genesis~ 217 {
mpi-genesis~ 218 if( w == v ) {
mpi-genesis~ 219 MPI vv = mpi_copy(v);
mpi-genesis~ 220 vv->sign = !vv->sign;
mpi-genesis~ 221 mpi_add( w, u, vv );
mpi-genesis~ 222 mpi_free(vv);
mpi-genesis~ 223 }
mpi-genesis~ 224 else {
mpi-genesis~ 225
mpi-genesis~ 226 v->sign = !v->sign;
mpi-genesis~ 227 mpi_add( w, u, v );
mpi-genesis~ 228 v->sign = !v->sign;
mpi-genesis~ 229 }
mpi-genesis~ 230 }
mpi-genesis~ 231
mpi-genesis~ 232
mpi-genesis~ 233 void
mpi-genesis~ 234 mpi_addm( MPI w, MPI u, MPI v, MPI m)
mpi-genesis~ 235 {
mpi-genesis~ 236 mpi_add(w, u, v);
mpi-genesis~ 237 mpi_fdiv_r( w, w, m );
mpi-genesis~ 238 }
mpi-genesis~ 239
mpi-genesis~ 240 void
mpi-genesis~ 241 mpi_subm( MPI w, MPI u, MPI v, MPI m)
mpi-genesis~ 242 {
mpi-genesis~ 243 mpi_sub(w, u, v);
mpi-genesis~ 244 mpi_fdiv_r( w, w, m );
mpi-genesis~ 245 }
mpi-genesis~ 246