lib/mpi/mpiutil.c

   1 /* mpiutil.ac  -  Utility functions for MPI
   2  * Copyright (C) 1998, 1999 Free Software Foundation, Inc.
   3  *
   4  * This file is part of GnuPG.
   5  *
   6  * GnuPG is free software; you can redistribute it and/or modify
   7  * it under the terms of the GNU General Public License as published by
   8  * the Free Software Foundation; either version 2 of the License, or
   9  * (at your option) any later version.
  10  *
  11  * GnuPG 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 General Public License for more details.
  15  *
  16  * You should have received a copy of the GNU General Public License
  17  * 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
  21 #include "mpi-internal.h"
  22
  23 /* Constants allocated right away at startup.  */
  24 static MPI constants[MPI_NUMBER_OF_CONSTANTS];
  25
  26 /* Initialize the MPI subsystem.  This is called early and allows to
  27  * do some initialization without taking care of threading issues.
  28  */
  29 static int __init mpi_init(void)
  30 {
  31         int idx;
  32         unsigned long value;
  33
  34         for (idx = 0; idx < MPI_NUMBER_OF_CONSTANTS; idx++) {
  35                 switch (idx) {
  36                 case MPI_C_ZERO:
  37                         value = 0;
  38                         break;
  39                 case MPI_C_ONE:
  40                         value = 1;
  41                         break;
  42                 case MPI_C_TWO:
  43                         value = 2;
  44                         break;
  45                 case MPI_C_THREE:
  46                         value = 3;
  47                         break;
  48                 case MPI_C_FOUR:
  49                         value = 4;
  50                         break;
  51                 case MPI_C_EIGHT:
  52                         value = 8;
  53                         break;
  54                 default:
  55                         pr_err("MPI: invalid mpi_const selector %d\n", idx);
  56                         return -EFAULT;
  57                 }
  58                 constants[idx] = mpi_alloc_set_ui(value);
  59                 constants[idx]->flags = (16|32);
  60         }
  61
  62         return 0;
  63 }
  64 postcore_initcall(mpi_init);
  65
  66 /* Return a constant MPI descripbed by NO which is one of the
  67  * MPI_C_xxx macros.  There is no need to copy this returned value; it
  68  * may be used directly.
  69  */
  70 MPI mpi_const(enum gcry_mpi_constants no)
  71 {
  72         if ((int)no < 0 || no > MPI_NUMBER_OF_CONSTANTS)
  73                 pr_err("MPI: invalid mpi_const selector %d\n", no);
  74         if (!constants[no])
  75                 pr_err("MPI: MPI subsystem not initialized\n");
  76         return constants[no];
  77 }
  78 EXPORT_SYMBOL_GPL(mpi_const);
  79
  80 /****************
  81  * Note:  It was a bad idea to use the number of limbs to allocate
  82  *        because on a alpha the limbs are large but we normally need
  83  *        integers of n bits - So we should change this to bits (or bytes).
  84  *
  85  *        But mpi_alloc is used in a lot of places :-)
  86  */
  87 MPI mpi_alloc(unsigned nlimbs)
  88 {
  89         MPI a;
  90
  91         a = kmalloc(sizeof *a, GFP_KERNEL);
  92         if (!a)
  93                 return a;
  94
  95         if (nlimbs) {
  96                 a->d = mpi_alloc_limb_space(nlimbs);
  97                 if (!a->d) {
  98                         kfree(a);
  99                         return NULL;
 100                 }
 101         } else {
 102                 a->d = NULL;
 103         }
 104
 105         a->alloced = nlimbs;
 106         a->nlimbs = 0;
 107         a->sign = 0;
 108         a->flags = 0;
 109         a->nbits = 0;
 110         return a;
 111 }
 112 EXPORT_SYMBOL_GPL(mpi_alloc);
 113
 114 mpi_ptr_t mpi_alloc_limb_space(unsigned nlimbs)
 115 {
 116         size_t len = nlimbs * sizeof(mpi_limb_t);
 117
 118         if (!len)
 119                 return NULL;
 120
 121         return kmalloc(len, GFP_KERNEL);
 122 }
 123
 124 void mpi_free_limb_space(mpi_ptr_t a)
 125 {
 126         if (!a)
 127                 return;
 128
 129         kfree_sensitive(a);
 130 }
 131
 132 void mpi_assign_limb_space(MPI a, mpi_ptr_t ap, unsigned nlimbs)
 133 {
 134         mpi_free_limb_space(a->d);
 135         a->d = ap;
 136         a->alloced = nlimbs;
 137 }
 138
 139 /****************
 140  * Resize the array of A to NLIMBS. the additional space is cleared
 141  * (set to 0) [done by m_realloc()]
 142  */
 143 int mpi_resize(MPI a, unsigned nlimbs)
 144 {
 145         void *p;
 146
 147         if (nlimbs <= a->alloced)
 148                 return 0;       /* no need to do it */
 149
 150         if (a->d) {
 151                 p = kcalloc(nlimbs, sizeof(mpi_limb_t), GFP_KERNEL);
 152                 if (!p)
 153                         return -ENOMEM;
 154                 memcpy(p, a->d, a->alloced * sizeof(mpi_limb_t));
 155                 kfree_sensitive(a->d);
 156                 a->d = p;
 157         } else {
 158                 a->d = kcalloc(nlimbs, sizeof(mpi_limb_t), GFP_KERNEL);
 159                 if (!a->d)
 160                         return -ENOMEM;
 161         }
 162         a->alloced = nlimbs;
 163         return 0;
 164 }
 165
 166 void mpi_clear(MPI a)
 167 {
 168         if (!a)
 169                 return;
 170         a->nlimbs = 0;
 171         a->flags = 0;
 172 }
 173 EXPORT_SYMBOL_GPL(mpi_clear);
 174
 175 void mpi_free(MPI a)
 176 {
 177         if (!a)
 178                 return;
 179
 180         if (a->flags & 4)
 181                 kfree_sensitive(a->d);
 182         else
 183                 mpi_free_limb_space(a->d);
 184
 185         if (a->flags & ~7)
 186                 pr_info("invalid flag value in mpi\n");
 187         kfree(a);
 188 }
 189 EXPORT_SYMBOL_GPL(mpi_free);
 190
 191 /****************
 192  * Note: This copy function should not interpret the MPI
 193  *       but copy it transparently.
 194  */
 195 MPI mpi_copy(MPI a)
 196 {
 197         int i;
 198         MPI b;
 199
 200         if (a) {
 201                 b = mpi_alloc(a->nlimbs);
 202                 b->nlimbs = a->nlimbs;
 203                 b->sign = a->sign;
 204                 b->flags = a->flags;
 205                 b->flags &= ~(16|32); /* Reset the immutable and constant flags. */
 206                 for (i = 0; i < b->nlimbs; i++)
 207                         b->d[i] = a->d[i];
 208         } else
 209                 b = NULL;
 210         return b;
 211 }
 212
 213 /****************
 214  * This function allocates an MPI which is optimized to hold
 215  * a value as large as the one given in the argument and allocates it
 216  * with the same flags as A.
 217  */
 218 MPI mpi_alloc_like(MPI a)
 219 {
 220         MPI b;
 221
 222         if (a) {
 223                 b = mpi_alloc(a->nlimbs);
 224                 b->nlimbs = 0;
 225                 b->sign = 0;
 226                 b->flags = a->flags;
 227         } else
 228                 b = NULL;
 229
 230         return b;
 231 }
 232
 233
 234 /* Set U into W and release U.  If W is NULL only U will be released. */
 235 void mpi_snatch(MPI w, MPI u)
 236 {
 237         if (w) {
 238                 mpi_assign_limb_space(w, u->d, u->alloced);
 239                 w->nlimbs = u->nlimbs;
 240                 w->sign   = u->sign;
 241                 w->flags  = u->flags;
 242                 u->alloced = 0;
 243                 u->nlimbs = 0;
 244                 u->d = NULL;
 245         }
 246         mpi_free(u);
 247 }
 248
 249
 250 MPI mpi_set(MPI w, MPI u)
 251 {
 252         mpi_ptr_t wp, up;
 253         mpi_size_t usize = u->nlimbs;
 254         int usign = u->sign;
 255
 256         if (!w)
 257                 w = mpi_alloc(mpi_get_nlimbs(u));
 258         RESIZE_IF_NEEDED(w, usize);
 259         wp = w->d;
 260         up = u->d;
 261         MPN_COPY(wp, up, usize);
 262         w->nlimbs = usize;
 263         w->flags = u->flags;
 264         w->flags &= ~(16|32); /* Reset the immutable and constant flags.  */
 265         w->sign = usign;
 266         return w;
 267 }
 268 EXPORT_SYMBOL_GPL(mpi_set);
 269
 270 MPI mpi_set_ui(MPI w, unsigned long u)
 271 {
 272         if (!w)
 273                 w = mpi_alloc(1);
 274         /* FIXME: If U is 0 we have no need to resize and thus possible
 275          * allocating the limbs.
 276          */
 277         RESIZE_IF_NEEDED(w, 1);
 278         w->d[0] = u;
 279         w->nlimbs = u ? 1 : 0;
 280         w->sign = 0;
 281         w->flags = 0;
 282         return w;
 283 }
 284 EXPORT_SYMBOL_GPL(mpi_set_ui);
 285
 286 MPI mpi_alloc_set_ui(unsigned long u)
 287 {
 288         MPI w = mpi_alloc(1);
 289         w->d[0] = u;
 290         w->nlimbs = u ? 1 : 0;
 291         w->sign = 0;
 292         return w;
 293 }
 294
 295 /****************
 296  * Swap the value of A and B, when SWAP is 1.
 297  * Leave the value when SWAP is 0.
 298  * This implementation should be constant-time regardless of SWAP.
 299  */
 300 void mpi_swap_cond(MPI a, MPI b, unsigned long swap)
 301 {
 302         mpi_size_t i;
 303         mpi_size_t nlimbs;
 304         mpi_limb_t mask = ((mpi_limb_t)0) - swap;
 305         mpi_limb_t x;
 306
 307         if (a->alloced > b->alloced)
 308                 nlimbs = b->alloced;
 309         else
 310                 nlimbs = a->alloced;
 311         if (a->nlimbs > nlimbs || b->nlimbs > nlimbs)
 312                 return;
 313
 314         for (i = 0; i < nlimbs; i++) {
 315                 x = mask & (a->d[i] ^ b->d[i]);
 316                 a->d[i] = a->d[i] ^ x;
 317                 b->d[i] = b->d[i] ^ x;
 318         }
 319
 320         x = mask & (a->nlimbs ^ b->nlimbs);
 321         a->nlimbs = a->nlimbs ^ x;
 322         b->nlimbs = b->nlimbs ^ x;
 323
 324         x = mask & (a->sign ^ b->sign);
 325         a->sign = a->sign ^ x;
 326         b->sign = b->sign ^ x;
 327 }
 328
 329 MODULE_DESCRIPTION("Multiprecision maths library");
 330 MODULE_LICENSE("GPL");