ch1_mpi 1
ch1_mpi 2 * Modified by No Such Labs. (C) 2015. See README.
ch1_mpi 3 *
ch1_mpi 4 * This file was originally part of Gnu Privacy Guard (GPG), ver. 1.4.10,
ch1_mpi 5 * SHA256(gnupg-1.4.10.tar.gz):
ch1_mpi 6 * 0bfd74660a2f6cedcf7d8256db4a63c996ffebbcdc2cf54397bfb72878c5a85a
ch1_mpi 7 * (C) 1994-2005 Free Software Foundation, Inc.
ch1_mpi 8 *
ch1_mpi 9 * This program is free software: you can redistribute it and/or modify
ch1_mpi 10 * it under the terms of the GNU General Public License as published by
ch1_mpi 11 * the Free Software Foundation, either version 3 of the License, or
ch1_mpi 12 * (at your option) any later version.
ch1_mpi 13 *
ch1_mpi 14 * This program is distributed in the hope that it will be useful,
ch1_mpi 15 * but WITHOUT ANY WARRANTY; without even the implied warranty of
ch1_mpi 16 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
ch1_mpi 17 * GNU General Public License for more details.
ch1_mpi 18 *
ch1_mpi 19 * You should have received a copy of the GNU General Public License
ch1_mpi 20 * along with this program. If not, see <http:
ch1_mpi 21 */
ch1_mpi 22
ch1_mpi 23 #include <stdio.h>
ch1_mpi 24 #include <stdlib.h>
ch1_mpi 25 #include <string.h>
ch1_mpi 26 #include <assert.h>
ch1_mpi 27
ch1_mpi 28 #include "knobs.h"
ch1_mpi 29 #include "mpi.h"
ch1_mpi 30 #include "mpi-internal.h"
ch1_mpi 31 #include "memory.h"
ch1_mpi 32 #include "util.h"
ch1_mpi 33
ch1_mpi 34
ch1_mpi 35 #ifdef M_DEBUG
ch1_mpi 36 #undef mpi_alloc
ch1_mpi 37 #undef mpi_alloc_secure
ch1_mpi 38 #undef mpi_free
ch1_mpi 39 #endif
ch1_mpi 40
ch1_mpi 41
ch1_mpi 42 * Note: It was a bad idea to use the number of limbs to allocate
ch1_mpi 43 * because on a alpha the limbs are large but we normally need
ch1_mpi 44 * integers of n bits - So we should chnage this to bits (or bytes).
ch1_mpi 45 *
ch1_mpi 46 * But mpi_alloc is used in a lot of places :-)
ch1_mpi 47 */
ch1_mpi 48 MPI
ch1_mpi 49 #ifdef M_DEBUG
ch1_mpi 50 mpi_debug_alloc( unsigned nlimbs, const char *info )
ch1_mpi 51 #else
ch1_mpi 52 mpi_alloc( unsigned nlimbs )
ch1_mpi 53 #endif
ch1_mpi 54 {
ch1_mpi 55 MPI a;
ch1_mpi 56
ch1_mpi 57 if( DBG_MEMORY )
ch1_mpi 58 log_debug("mpi_alloc(%u)\n", nlimbs*BITS_PER_MPI_LIMB );
ch1_mpi 59 #ifdef M_DEBUG
ch1_mpi 60 a = m_debug_alloc( sizeof *a, info );
ch1_mpi 61 a->d = nlimbs? mpi_debug_alloc_limb_space( nlimbs, 0, info ) : NULL;
ch1_mpi 62 #else
ch1_mpi 63 a = xmalloc( sizeof *a );
ch1_mpi 64 a->d = nlimbs? mpi_alloc_limb_space( nlimbs, 0 ) : NULL;
ch1_mpi 65 #endif
ch1_mpi 66 a->alloced = nlimbs;
ch1_mpi 67 a->nlimbs = 0;
ch1_mpi 68 a->sign = 0;
ch1_mpi 69 a->flags = 0;
ch1_mpi 70 a->nbits = 0;
ch1_mpi 71 return a;
ch1_mpi 72 }
ch1_mpi 73
ch1_mpi 74 void
ch1_mpi 75 mpi_m_check( MPI a )
ch1_mpi 76 {
ch1_mpi 77 m_check(a);
ch1_mpi 78 m_check(a->d);
ch1_mpi 79 }
ch1_mpi 80
ch1_mpi 81 MPI
ch1_mpi 82 #ifdef M_DEBUG
ch1_mpi 83 mpi_debug_alloc_secure( unsigned nlimbs, const char *info )
ch1_mpi 84 #else
ch1_mpi 85 mpi_alloc_secure( unsigned nlimbs )
ch1_mpi 86 #endif
ch1_mpi 87 {
ch1_mpi 88 MPI a;
ch1_mpi 89
ch1_mpi 90 if( DBG_MEMORY )
ch1_mpi 91 log_debug("mpi_alloc_secure(%u)\n", nlimbs*BITS_PER_MPI_LIMB );
ch1_mpi 92 #ifdef M_DEBUG
ch1_mpi 93 a = m_debug_alloc( sizeof *a, info );
ch1_mpi 94 a->d = nlimbs? mpi_debug_alloc_limb_space( nlimbs, 1, info ) : NULL;
ch1_mpi 95 #else
ch1_mpi 96 a = xmalloc( sizeof *a );
ch1_mpi 97 a->d = nlimbs? mpi_alloc_limb_space( nlimbs, 1 ) : NULL;
ch1_mpi 98 #endif
ch1_mpi 99 a->alloced = nlimbs;
ch1_mpi 100 a->flags = 1;
ch1_mpi 101 a->nlimbs = 0;
ch1_mpi 102 a->sign = 0;
ch1_mpi 103 a->nbits = 0;
ch1_mpi 104 return a;
ch1_mpi 105 }
ch1_mpi 106
ch1_mpi 107
ch1_mpi 108 #if 0
ch1_mpi 109 static void *unused_limbs_5;
ch1_mpi 110 static void *unused_limbs_32;
ch1_mpi 111 static void *unused_limbs_64;
ch1_mpi 112 #endif
ch1_mpi 113
ch1_mpi 114 mpi_ptr_t
ch1_mpi 115 #ifdef M_DEBUG
ch1_mpi 116 mpi_debug_alloc_limb_space( unsigned nlimbs, int secure, const char *info )
ch1_mpi 117 #else
ch1_mpi 118 mpi_alloc_limb_space( unsigned nlimbs, int secure )
ch1_mpi 119 #endif
ch1_mpi 120 {
ch1_mpi 121 size_t len = nlimbs * sizeof(mpi_limb_t);
ch1_mpi 122 mpi_ptr_t p;
ch1_mpi 123
ch1_mpi 124 if( DBG_MEMORY )
ch1_mpi 125 log_debug("mpi_alloc_limb_space(%u)\n", (unsigned)len*8 );
ch1_mpi 126 #if 0
ch1_mpi 127 if( !secure ) {
ch1_mpi 128 if( nlimbs == 5 && unused_limbs_5 ) {
ch1_mpi 129 p = unused_limbs_5;
ch1_mpi 130 unused_limbs_5 = *p;
ch1_mpi 131 return p;
ch1_mpi 132 }
ch1_mpi 133 else if( nlimbs == 32 && unused_limbs_32 ) {
ch1_mpi 134 p = unused_limbs_32;
ch1_mpi 135 unused_limbs_32 = *p;
ch1_mpi 136 return p;
ch1_mpi 137 }
ch1_mpi 138 else if( nlimbs == 64 && unused_limbs_64 ) {
ch1_mpi 139 p = unused_limbs_64;
ch1_mpi 140 unused_limbs_64 = *p;
ch1_mpi 141 return p;
ch1_mpi 142 }
ch1_mpi 143 }
ch1_mpi 144 #endif
ch1_mpi 145
ch1_mpi 146 #ifdef M_DEBUG
ch1_mpi 147 p = secure? m_debug_alloc_secure(len, info):m_debug_alloc( len, info );
ch1_mpi 148 #else
ch1_mpi 149 p = secure? xmalloc_secure( len ):xmalloc( len );
ch1_mpi 150 #endif
ch1_mpi 151
ch1_mpi 152 return p;
ch1_mpi 153 }
ch1_mpi 154
ch1_mpi 155 void
ch1_mpi 156 #ifdef M_DEBUG
ch1_mpi 157 mpi_debug_free_limb_space( mpi_ptr_t a, const char *info )
ch1_mpi 158 #else
ch1_mpi 159 mpi_free_limb_space( mpi_ptr_t a )
ch1_mpi 160 #endif
ch1_mpi 161 {
ch1_mpi 162 if( !a )
ch1_mpi 163 return;
ch1_mpi 164 if( DBG_MEMORY )
ch1_mpi 165 log_debug("mpi_free_limb_space of size %lu\n", (ulong)m_size(a)*8 );
ch1_mpi 166
ch1_mpi 167 #if 0
ch1_mpi 168 if( !m_is_secure(a) ) {
ch1_mpi 169 size_t nlimbs = m_size(a) / 4 ;
ch1_mpi 170 void *p = a;
ch1_mpi 171
ch1_mpi 172 if( nlimbs == 5 ) {
ch1_mpi 173 *a = unused_limbs_5;
ch1_mpi 174 unused_limbs_5 = a;
ch1_mpi 175 return;
ch1_mpi 176 }
ch1_mpi 177 else if( nlimbs == 32 ) {
ch1_mpi 178 *a = unused_limbs_32;
ch1_mpi 179 unused_limbs_32 = a;
ch1_mpi 180 return;
ch1_mpi 181 }
ch1_mpi 182 else if( nlimbs == 64 ) {
ch1_mpi 183 *a = unused_limbs_64;
ch1_mpi 184 unused_limbs_64 = a;
ch1_mpi 185 return;
ch1_mpi 186 }
ch1_mpi 187 }
ch1_mpi 188 #endif
ch1_mpi 189
ch1_mpi 190 xfree(a);
ch1_mpi 191 }
ch1_mpi 192
ch1_mpi 193
ch1_mpi 194 void
ch1_mpi 195 mpi_assign_limb_space( MPI a, mpi_ptr_t ap, unsigned nlimbs )
ch1_mpi 196 {
ch1_mpi 197 mpi_free_limb_space(a->d);
ch1_mpi 198 a->d = ap;
ch1_mpi 199 a->alloced = nlimbs;
ch1_mpi 200 }
ch1_mpi 201
ch1_mpi 202
ch1_mpi 203
ch1_mpi 204
ch1_mpi 205 * Resize the array of A to NLIMBS. the additional space is cleared
ch1_mpi 206 * (set to 0) [done by xrealloc()]
ch1_mpi 207 */
ch1_mpi 208 void
ch1_mpi 209 #ifdef M_DEBUG
ch1_mpi 210 mpi_debug_resize( MPI a, unsigned nlimbs, const char *info )
ch1_mpi 211 #else
ch1_mpi 212 mpi_resize( MPI a, unsigned nlimbs )
ch1_mpi 213 #endif
ch1_mpi 214 {
ch1_mpi 215 if( nlimbs <= a->alloced )
ch1_mpi 216 return;
ch1_mpi 217
ch1_mpi 218 * take care of it. Maybe we should drop a->secure completely
ch1_mpi 219 * and rely on a mpi_is_secure function, which would be
ch1_mpi 220 * a wrapper around m_is_secure
ch1_mpi 221 */
ch1_mpi 222 #ifdef M_DEBUG
ch1_mpi 223 if( a->d )
ch1_mpi 224 a->d = m_debug_realloc(a->d, nlimbs * sizeof(mpi_limb_t), info );
ch1_mpi 225 else
ch1_mpi 226 a->d = m_debug_alloc_clear( nlimbs * sizeof(mpi_limb_t), info );
ch1_mpi 227 #else
ch1_mpi 228 if( a->d )
ch1_mpi 229 a->d = xrealloc(a->d, nlimbs * sizeof(mpi_limb_t) );
ch1_mpi 230 else
ch1_mpi 231 a->d = xmalloc_clear( nlimbs * sizeof(mpi_limb_t) );
ch1_mpi 232 #endif
ch1_mpi 233 a->alloced = nlimbs;
ch1_mpi 234 }
ch1_mpi 235
ch1_mpi 236 void
ch1_mpi 237 mpi_clear( MPI a )
ch1_mpi 238 {
ch1_mpi 239 a->nlimbs = 0;
ch1_mpi 240 a->nbits = 0;
ch1_mpi 241 a->flags = 0;
ch1_mpi 242 }
ch1_mpi 243
ch1_mpi 244
ch1_mpi 245 void
ch1_mpi 246 #ifdef M_DEBUG
ch1_mpi 247 mpi_debug_free( MPI a, const char *info )
ch1_mpi 248 #else
ch1_mpi 249 mpi_free( MPI a )
ch1_mpi 250 #endif
ch1_mpi 251 {
ch1_mpi 252 if( !a )
ch1_mpi 253 return;
ch1_mpi 254 if( DBG_MEMORY )
ch1_mpi 255 log_debug("mpi_free\n" );
ch1_mpi 256 if( a->flags & 4 )
ch1_mpi 257 xfree( a->d );
ch1_mpi 258 else {
ch1_mpi 259 #ifdef M_DEBUG
ch1_mpi 260 mpi_debug_free_limb_space(a->d, info);
ch1_mpi 261 #else
ch1_mpi 262 mpi_free_limb_space(a->d);
ch1_mpi 263 #endif
ch1_mpi 264 }
ch1_mpi 265 if( a->flags & ~7 )
ch1_mpi 266 log_bug("invalid flag value in mpi\n");
ch1_mpi 267 xfree(a);
ch1_mpi 268 }
ch1_mpi 269
ch1_mpi 270
ch1_mpi 271 void
ch1_mpi 272 mpi_set_secure( MPI a )
ch1_mpi 273 {
ch1_mpi 274 mpi_ptr_t ap, bp;
ch1_mpi 275
ch1_mpi 276 if( (a->flags & 1) )
ch1_mpi 277 return;
ch1_mpi 278 a->flags |= 1;
ch1_mpi 279 ap = a->d;
ch1_mpi 280 if( !a->nlimbs ) {
ch1_mpi 281 assert(!ap);
ch1_mpi 282 return;
ch1_mpi 283 }
ch1_mpi 284 #ifdef M_DEBUG
ch1_mpi 285 bp = mpi_debug_alloc_limb_space( a->nlimbs, 1, "set_secure" );
ch1_mpi 286 #else
ch1_mpi 287 bp = mpi_alloc_limb_space( a->nlimbs, 1 );
ch1_mpi 288 #endif
ch1_mpi 289 MPN_COPY( bp, ap, a->nlimbs );
ch1_mpi 290 a->d = bp;
ch1_mpi 291 #ifdef M_DEBUG
ch1_mpi 292 mpi_debug_free_limb_space(ap, "set_secure");
ch1_mpi 293 #else
ch1_mpi 294 mpi_free_limb_space(ap);
ch1_mpi 295 #endif
ch1_mpi 296 }
ch1_mpi 297
ch1_mpi 298
ch1_mpi 299 MPI
ch1_mpi 300 mpi_set_opaque( MPI a, void *p, unsigned int len )
ch1_mpi 301 {
ch1_mpi 302 if( !a ) {
ch1_mpi 303 #ifdef M_DEBUG
ch1_mpi 304 a = mpi_debug_alloc(0,"alloc_opaque");
ch1_mpi 305 #else
ch1_mpi 306 a = mpi_alloc(0);
ch1_mpi 307 #endif
ch1_mpi 308 }
ch1_mpi 309
ch1_mpi 310 if( a->flags & 4 )
ch1_mpi 311 xfree( a->d );
ch1_mpi 312 else {
ch1_mpi 313 #ifdef M_DEBUG
ch1_mpi 314 mpi_debug_free_limb_space(a->d, "alloc_opaque");
ch1_mpi 315 #else
ch1_mpi 316 mpi_free_limb_space(a->d);
ch1_mpi 317 #endif
ch1_mpi 318 }
ch1_mpi 319
ch1_mpi 320 a->d = p;
ch1_mpi 321 a->alloced = 0;
ch1_mpi 322 a->nlimbs = 0;
ch1_mpi 323 a->nbits = len;
ch1_mpi 324 a->flags = 4;
ch1_mpi 325 return a;
ch1_mpi 326 }
ch1_mpi 327
ch1_mpi 328
ch1_mpi 329 void *
ch1_mpi 330 mpi_get_opaque( MPI a, unsigned int *len )
ch1_mpi 331 {
ch1_mpi 332 if( !(a->flags & 4) )
ch1_mpi 333 log_bug("mpi_get_opaque on normal mpi\n");
ch1_mpi 334 if( len )
ch1_mpi 335 *len = a->nbits;
ch1_mpi 336 return a->d;
ch1_mpi 337 }
ch1_mpi 338
ch1_mpi 339
ch1_mpi 340
ch1_mpi 341 * Note: This copy function should not interpret the MPI
ch1_mpi 342 * but copy it transparently.
ch1_mpi 343 */
ch1_mpi 344 MPI
ch1_mpi 345 #ifdef M_DEBUG
ch1_mpi 346 mpi_debug_copy( MPI a, const char *info )
ch1_mpi 347 #else
ch1_mpi 348 mpi_copy( MPI a )
ch1_mpi 349 #endif
ch1_mpi 350 {
ch1_mpi 351 int i;
ch1_mpi 352 MPI b;
ch1_mpi 353
ch1_mpi 354 if( a && (a->flags & 4) ) {
ch1_mpi 355 void *p = m_is_secure(a->d)? xmalloc_secure( a->nbits )
ch1_mpi 356 : xmalloc( a->nbits );
ch1_mpi 357 memcpy( p, a->d, a->nbits );
ch1_mpi 358 b = mpi_set_opaque( NULL, p, a->nbits );
ch1_mpi 359 }
ch1_mpi 360 else if( a ) {
ch1_mpi 361 #ifdef M_DEBUG
ch1_mpi 362 b = mpi_is_secure(a)? mpi_debug_alloc_secure( a->nlimbs, info )
ch1_mpi 363 : mpi_debug_alloc( a->nlimbs, info );
ch1_mpi 364 #else
ch1_mpi 365 b = mpi_is_secure(a)? mpi_alloc_secure( a->nlimbs )
ch1_mpi 366 : mpi_alloc( a->nlimbs );
ch1_mpi 367 #endif
ch1_mpi 368 b->nlimbs = a->nlimbs;
ch1_mpi 369 b->sign = a->sign;
ch1_mpi 370 b->flags = a->flags;
ch1_mpi 371 b->nbits = a->nbits;
ch1_mpi 372 for(i=0; i < b->nlimbs; i++ )
ch1_mpi 373 b->d[i] = a->d[i];
ch1_mpi 374 }
ch1_mpi 375 else
ch1_mpi 376 b = NULL;
ch1_mpi 377 return b;
ch1_mpi 378 }
ch1_mpi 379
ch1_mpi 380
ch1_mpi 381
ch1_mpi 382 * This function allocates an MPI which is optimized to hold
ch1_mpi 383 * a value as large as the one given in the argument and allocates it
ch1_mpi 384 * with the same flags as A.
ch1_mpi 385 */
ch1_mpi 386 MPI
ch1_mpi 387 #ifdef M_DEBUG
ch1_mpi 388 mpi_debug_alloc_like( MPI a, const char *info )
ch1_mpi 389 #else
ch1_mpi 390 mpi_alloc_like( MPI a )
ch1_mpi 391 #endif
ch1_mpi 392 {
ch1_mpi 393 MPI b;
ch1_mpi 394
ch1_mpi 395 if( a && (a->flags & 4) ) {
ch1_mpi 396 void *p = m_is_secure(a->d)? xmalloc_secure( a->nbits )
ch1_mpi 397 : xmalloc( a->nbits );
ch1_mpi 398 memcpy( p, a->d, a->nbits );
ch1_mpi 399 b = mpi_set_opaque( NULL, p, a->nbits );
ch1_mpi 400 }
ch1_mpi 401 else if( a ) {
ch1_mpi 402 #ifdef M_DEBUG
ch1_mpi 403 b = mpi_is_secure(a)? mpi_debug_alloc_secure( a->nlimbs, info )
ch1_mpi 404 : mpi_debug_alloc( a->nlimbs, info );
ch1_mpi 405 #else
ch1_mpi 406 b = mpi_is_secure(a)? mpi_alloc_secure( a->nlimbs )
ch1_mpi 407 : mpi_alloc( a->nlimbs );
ch1_mpi 408 #endif
ch1_mpi 409 b->nlimbs = 0;
ch1_mpi 410 b->sign = 0;
ch1_mpi 411 b->flags = a->flags;
ch1_mpi 412 b->nbits = 0;
ch1_mpi 413 }
ch1_mpi 414 else
ch1_mpi 415 b = NULL;
ch1_mpi 416 return b;
ch1_mpi 417 }
ch1_mpi 418
ch1_mpi 419
ch1_mpi 420 void
ch1_mpi 421 mpi_set( MPI w, MPI u)
ch1_mpi 422 {
ch1_mpi 423 mpi_ptr_t wp, up;
ch1_mpi 424 mpi_size_t usize = u->nlimbs;
ch1_mpi 425 int usign = u->sign;
ch1_mpi 426
ch1_mpi 427 RESIZE_IF_NEEDED(w, usize);
ch1_mpi 428 wp = w->d;
ch1_mpi 429 up = u->d;
ch1_mpi 430 MPN_COPY( wp, up, usize );
ch1_mpi 431 w->nlimbs = usize;
ch1_mpi 432 w->nbits = u->nbits;
ch1_mpi 433 w->flags = u->flags;
ch1_mpi 434 w->sign = usign;
ch1_mpi 435 }
ch1_mpi 436
ch1_mpi 437
ch1_mpi 438 void
ch1_mpi 439 mpi_set_ui( MPI w, unsigned long u)
ch1_mpi 440 {
ch1_mpi 441 RESIZE_IF_NEEDED(w, 1);
ch1_mpi 442 w->d[0] = u;
ch1_mpi 443 w->nlimbs = u? 1:0;
ch1_mpi 444 w->sign = 0;
ch1_mpi 445 w->nbits = 0;
ch1_mpi 446 w->flags = 0;
ch1_mpi 447 }
ch1_mpi 448
ch1_mpi 449
ch1_mpi 450 MPI
ch1_mpi 451 mpi_alloc_set_ui( unsigned long u)
ch1_mpi 452 {
ch1_mpi 453 #ifdef M_DEBUG
ch1_mpi 454 MPI w = mpi_debug_alloc(1,"alloc_set_ui");
ch1_mpi 455 #else
ch1_mpi 456 MPI w = mpi_alloc(1);
ch1_mpi 457 #endif
ch1_mpi 458 w->d[0] = u;
ch1_mpi 459 w->nlimbs = u? 1:0;
ch1_mpi 460 w->sign = 0;
ch1_mpi 461 return w;
ch1_mpi 462 }
ch1_mpi 463
ch1_mpi 464
ch1_mpi 465 void
ch1_mpi 466 mpi_swap( MPI a, MPI b)
ch1_mpi 467 {
ch1_mpi 468 struct gcry_mpi tmp;
ch1_mpi 469
ch1_mpi 470 tmp = *a; *a = *b; *b = tmp;
ch1_mpi 471 }
ch1_mpi 472
ch1_mpi 473
ch1_mpi 474 int
ch1_mpi 475 mpi_get_nlimbs (MPI a)
ch1_mpi 476 {
ch1_mpi 477 return a->nlimbs;
ch1_mpi 478 }
ch1_mpi 479
ch1_mpi 480
ch1_mpi 481 int
ch1_mpi 482 mpi_is_neg (MPI a)
ch1_mpi 483 {
ch1_mpi 484 return a->sign;
ch1_mpi 485 }
ch1_mpi 486
ch1_mpi 487
ch1_mpi 488
ch1_mpi 489 the number of bytes to represent it. */
ch1_mpi 490 unsigned int
ch1_mpi 491 mpi_nlimb_hint_from_nbytes (unsigned int nbytes)
ch1_mpi 492 {
ch1_mpi 493 return (nbytes+BYTES_PER_MPI_LIMB-1) / BYTES_PER_MPI_LIMB;
ch1_mpi 494 }
ch1_mpi 495
ch1_mpi 496
ch1_mpi 497 the number of bytes to represent it. */
ch1_mpi 498 unsigned int
ch1_mpi 499 mpi_nlimb_hint_from_nbits (unsigned int nbits)
ch1_mpi 500 {
ch1_mpi 501 return (nbits+BITS_PER_MPI_LIMB-1) / BITS_PER_MPI_LIMB;
ch1_mpi 502 }
ch1_mpi 503
ch1_mpi 504 unsigned int
ch1_mpi 505 mpi_get_flags (MPI a)
ch1_mpi 506 {
ch1_mpi 507 return a->flags;
ch1_mpi 508 }