crypto: GnuPG based MPI lib - source files (part 1)
Dmitry Kasatkin [Wed, 31 Aug 2011 11:05:16 +0000 (14:05 +0300)]
Adds the multi-precision-integer maths library which was originally taken
from GnuPG and ported to the kernel by (among others) David Howells.
This version is taken from Fedora kernel 2.6.32-71.14.1.el6.
The difference is that checkpatch reported errors and warnings have been fixed.

This library is used to implemenet RSA digital signature verification
used in IMA/EVM integrity protection subsystem.

Due to patch size limitation, the patch is divided into 4 parts.

Signed-off-by: Dmitry Kasatkin <dmitry.kasatkin@intel.com>

14 files changed:
lib/mpi/generic_mpih-add1.c [new file with mode: 0644]
lib/mpi/generic_mpih-lshift.c [new file with mode: 0644]
lib/mpi/generic_mpih-mul1.c [new file with mode: 0644]
lib/mpi/generic_mpih-mul2.c [new file with mode: 0644]
lib/mpi/generic_mpih-mul3.c [new file with mode: 0644]
lib/mpi/generic_mpih-rshift.c [new file with mode: 0644]
lib/mpi/generic_mpih-sub1.c [new file with mode: 0644]
lib/mpi/mpi-bit.c [new file with mode: 0644]
lib/mpi/mpi-pow.c [new file with mode: 0644]
lib/mpi/mpicoder.c [new file with mode: 0644]
lib/mpi/mpih-cmp.c [new file with mode: 0644]
lib/mpi/mpih-div.c [new file with mode: 0644]
lib/mpi/mpih-mul.c [new file with mode: 0644]
lib/mpi/mpiutil.c [new file with mode: 0644]

diff --git a/lib/mpi/generic_mpih-add1.c b/lib/mpi/generic_mpih-add1.c
new file mode 100644 (file)
index 0000000..c94c7dd
--- /dev/null
@@ -0,0 +1,61 @@
+/* mpihelp-add_1.c  -  MPI helper functions
+ * Copyright (C) 1994, 1996, 1997, 1998,
+ *               2000 Free Software Foundation, Inc.
+ *
+ * This file is part of GnuPG.
+ *
+ * GnuPG is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation; either version 2 of the License, or
+ * (at your option) any later version.
+ *
+ * GnuPG is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software
+ * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA
+ *
+ * Note: This code is heavily based on the GNU MP Library.
+ *      Actually it's the same code with only minor changes in the
+ *      way the data is stored; this is to support the abstraction
+ *      of an optional secure memory allocation which may be used
+ *      to avoid revealing of sensitive data due to paging etc.
+ *      The GNU MP Library itself is published under the LGPL;
+ *      however I decided to publish this code under the plain GPL.
+ */
+
+#include "mpi-internal.h"
+#include "longlong.h"
+
+mpi_limb_t
+mpihelp_add_n(mpi_ptr_t res_ptr, mpi_ptr_t s1_ptr,
+             mpi_ptr_t s2_ptr, mpi_size_t size)
+{
+       mpi_limb_t x, y, cy;
+       mpi_size_t j;
+
+       /* The loop counter and index J goes from -SIZE to -1.  This way
+          the loop becomes faster.  */
+       j = -size;
+
+       /* Offset the base pointers to compensate for the negative indices. */
+       s1_ptr -= j;
+       s2_ptr -= j;
+       res_ptr -= j;
+
+       cy = 0;
+       do {
+               y = s2_ptr[j];
+               x = s1_ptr[j];
+               y += cy;        /* add previous carry to one addend */
+               cy = y < cy;    /* get out carry from that addition */
+               y += x;         /* add other addend */
+               cy += y < x;    /* get out carry from that add, combine */
+               res_ptr[j] = y;
+       } while (++j);
+
+       return cy;
+}
diff --git a/lib/mpi/generic_mpih-lshift.c b/lib/mpi/generic_mpih-lshift.c
new file mode 100644 (file)
index 0000000..8631892
--- /dev/null
@@ -0,0 +1,63 @@
+/* mpihelp-lshift.c  - MPI helper functions
+ * Copyright (C) 1994, 1996, 1998, 2001 Free Software Foundation, Inc.
+ *
+ * This file is part of GnuPG.
+ *
+ * GnuPG is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation; either version 2 of the License, or
+ * (at your option) any later version.
+ *
+ * GnuPG is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software
+ * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA
+ *
+ * Note: This code is heavily based on the GNU MP Library.
+ *      Actually it's the same code with only minor changes in the
+ *      way the data is stored; this is to support the abstraction
+ *      of an optional secure memory allocation which may be used
+ *      to avoid revealing of sensitive data due to paging etc.
+ *      The GNU MP Library itself is published under the LGPL;
+ *      however I decided to publish this code under the plain GPL.
+ */
+
+#include "mpi-internal.h"
+
+/* Shift U (pointed to by UP and USIZE digits long) CNT bits to the left
+ * and store the USIZE least significant digits of the result at WP.
+ * Return the bits shifted out from the most significant digit.
+ *
+ * Argument constraints:
+ * 1. 0 < CNT < BITS_PER_MP_LIMB
+ * 2. If the result is to be written over the input, WP must be >= UP.
+ */
+
+mpi_limb_t
+mpihelp_lshift(mpi_ptr_t wp, mpi_ptr_t up, mpi_size_t usize, unsigned int cnt)
+{
+       mpi_limb_t high_limb, low_limb;
+       unsigned sh_1, sh_2;
+       mpi_size_t i;
+       mpi_limb_t retval;
+
+       sh_1 = cnt;
+       wp += 1;
+       sh_2 = BITS_PER_MPI_LIMB - sh_1;
+       i = usize - 1;
+       low_limb = up[i];
+       retval = low_limb >> sh_2;
+       high_limb = low_limb;
+       while (--i >= 0) {
+               low_limb = up[i];
+               wp[i] = (high_limb << sh_1) | (low_limb >> sh_2);
+               high_limb = low_limb;
+       }
+       wp[i] = high_limb << sh_1;
+
+       return retval;
+}
diff --git a/lib/mpi/generic_mpih-mul1.c b/lib/mpi/generic_mpih-mul1.c
new file mode 100644 (file)
index 0000000..1668dfd
--- /dev/null
@@ -0,0 +1,57 @@
+/* mpihelp-mul_1.c  -  MPI helper functions
+ * Copyright (C) 1994, 1996, 1997, 1998, 2001 Free Software Foundation, Inc.
+ *
+ * This file is part of GnuPG.
+ *
+ * GnuPG is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation; either version 2 of the License, or
+ * (at your option) any later version.
+ *
+ * GnuPG is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software
+ * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA
+ *
+ * Note: This code is heavily based on the GNU MP Library.
+ *      Actually it's the same code with only minor changes in the
+ *      way the data is stored; this is to support the abstraction
+ *      of an optional secure memory allocation which may be used
+ *      to avoid revealing of sensitive data due to paging etc.
+ *      The GNU MP Library itself is published under the LGPL;
+ *      however I decided to publish this code under the plain GPL.
+ */
+
+#include "mpi-internal.h"
+#include "longlong.h"
+
+mpi_limb_t
+mpihelp_mul_1(mpi_ptr_t res_ptr, mpi_ptr_t s1_ptr, mpi_size_t s1_size,
+             mpi_limb_t s2_limb)
+{
+       mpi_limb_t cy_limb;
+       mpi_size_t j;
+       mpi_limb_t prod_high, prod_low;
+
+       /* The loop counter and index J goes from -S1_SIZE to -1.  This way
+        * the loop becomes faster.  */
+       j = -s1_size;
+
+       /* Offset the base pointers to compensate for the negative indices.  */
+       s1_ptr -= j;
+       res_ptr -= j;
+
+       cy_limb = 0;
+       do {
+               umul_ppmm(prod_high, prod_low, s1_ptr[j], s2_limb);
+               prod_low += cy_limb;
+               cy_limb = (prod_low < cy_limb ? 1 : 0) + prod_high;
+               res_ptr[j] = prod_low;
+       } while (++j);
+
+       return cy_limb;
+}
diff --git a/lib/mpi/generic_mpih-mul2.c b/lib/mpi/generic_mpih-mul2.c
new file mode 100644 (file)
index 0000000..8a7b29e
--- /dev/null
@@ -0,0 +1,60 @@
+/* mpihelp-mul_2.c  -  MPI helper functions
+ * Copyright (C) 1994, 1996, 1997, 1998, 2001 Free Software Foundation, Inc.
+ *
+ * This file is part of GnuPG.
+ *
+ * GnuPG is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation; either version 2 of the License, or
+ * (at your option) any later version.
+ *
+ * GnuPG is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software
+ * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA
+ *
+ * Note: This code is heavily based on the GNU MP Library.
+ *      Actually it's the same code with only minor changes in the
+ *      way the data is stored; this is to support the abstraction
+ *      of an optional secure memory allocation which may be used
+ *      to avoid revealing of sensitive data due to paging etc.
+ *      The GNU MP Library itself is published under the LGPL;
+ *      however I decided to publish this code under the plain GPL.
+ */
+
+#include "mpi-internal.h"
+#include "longlong.h"
+
+mpi_limb_t
+mpihelp_addmul_1(mpi_ptr_t res_ptr, mpi_ptr_t s1_ptr,
+                mpi_size_t s1_size, mpi_limb_t s2_limb)
+{
+       mpi_limb_t cy_limb;
+       mpi_size_t j;
+       mpi_limb_t prod_high, prod_low;
+       mpi_limb_t x;
+
+       /* The loop counter and index J goes from -SIZE to -1.  This way
+        * the loop becomes faster.  */
+       j = -s1_size;
+       res_ptr -= j;
+       s1_ptr -= j;
+
+       cy_limb = 0;
+       do {
+               umul_ppmm(prod_high, prod_low, s1_ptr[j], s2_limb);
+
+               prod_low += cy_limb;
+               cy_limb = (prod_low < cy_limb ? 1 : 0) + prod_high;
+
+               x = res_ptr[j];
+               prod_low = x + prod_low;
+               cy_limb += prod_low < x ? 1 : 0;
+               res_ptr[j] = prod_low;
+       } while (++j);
+       return cy_limb;
+}
diff --git a/lib/mpi/generic_mpih-mul3.c b/lib/mpi/generic_mpih-mul3.c
new file mode 100644 (file)
index 0000000..f96df32
--- /dev/null
@@ -0,0 +1,61 @@
+/* mpihelp-mul_3.c  -  MPI helper functions
+ * Copyright (C) 1994, 1996, 1997, 1998, 2001 Free Software Foundation, Inc.
+ *
+ * This file is part of GnuPG.
+ *
+ * GnuPG is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation; either version 2 of the License, or
+ * (at your option) any later version.
+ *
+ * GnuPG is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software
+ * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA
+ *
+ * Note: This code is heavily based on the GNU MP Library.
+ *      Actually it's the same code with only minor changes in the
+ *      way the data is stored; this is to support the abstraction
+ *      of an optional secure memory allocation which may be used
+ *      to avoid revealing of sensitive data due to paging etc.
+ *      The GNU MP Library itself is published under the LGPL;
+ *      however I decided to publish this code under the plain GPL.
+ */
+
+#include "mpi-internal.h"
+#include "longlong.h"
+
+mpi_limb_t
+mpihelp_submul_1(mpi_ptr_t res_ptr, mpi_ptr_t s1_ptr,
+                mpi_size_t s1_size, mpi_limb_t s2_limb)
+{
+       mpi_limb_t cy_limb;
+       mpi_size_t j;
+       mpi_limb_t prod_high, prod_low;
+       mpi_limb_t x;
+
+       /* The loop counter and index J goes from -SIZE to -1.  This way
+        * the loop becomes faster.  */
+       j = -s1_size;
+       res_ptr -= j;
+       s1_ptr -= j;
+
+       cy_limb = 0;
+       do {
+               umul_ppmm(prod_high, prod_low, s1_ptr[j], s2_limb);
+
+               prod_low += cy_limb;
+               cy_limb = (prod_low < cy_limb ? 1 : 0) + prod_high;
+
+               x = res_ptr[j];
+               prod_low = x - prod_low;
+               cy_limb += prod_low > x ? 1 : 0;
+               res_ptr[j] = prod_low;
+       } while (++j);
+
+       return cy_limb;
+}
diff --git a/lib/mpi/generic_mpih-rshift.c b/lib/mpi/generic_mpih-rshift.c
new file mode 100644 (file)
index 0000000..ffa3288
--- /dev/null
@@ -0,0 +1,63 @@
+/* mpih-rshift.c  -  MPI helper functions
+ * Copyright (C) 1994, 1996, 1998, 1999,
+ *               2000, 2001 Free Software Foundation, Inc.
+ *
+ * This file is part of GNUPG
+ *
+ * GNUPG is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation; either version 2 of the License, or
+ * (at your option) any later version.
+ *
+ * GNUPG is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software
+ * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA
+ *
+ * Note: This code is heavily based on the GNU MP Library.
+ *      Actually it's the same code with only minor changes in the
+ *      way the data is stored; this is to support the abstraction
+ *      of an optional secure memory allocation which may be used
+ *      to avoid revealing of sensitive data due to paging etc.
+ *      The GNU MP Library itself is published under the LGPL;
+ *      however I decided to publish this code under the plain GPL.
+ */
+
+#include "mpi-internal.h"
+
+/* Shift U (pointed to by UP and USIZE limbs long) CNT bits to the right
+ * and store the USIZE least significant limbs of the result at WP.
+ * The bits shifted out to the right are returned.
+ *
+ * Argument constraints:
+ * 1. 0 < CNT < BITS_PER_MP_LIMB
+ * 2. If the result is to be written over the input, WP must be <= UP.
+ */
+
+mpi_limb_t
+mpihelp_rshift(mpi_ptr_t wp, mpi_ptr_t up, mpi_size_t usize, unsigned cnt)
+{
+       mpi_limb_t high_limb, low_limb;
+       unsigned sh_1, sh_2;
+       mpi_size_t i;
+       mpi_limb_t retval;
+
+       sh_1 = cnt;
+       wp -= 1;
+       sh_2 = BITS_PER_MPI_LIMB - sh_1;
+       high_limb = up[0];
+       retval = high_limb << sh_2;
+       low_limb = high_limb;
+       for (i = 1; i < usize; i++) {
+               high_limb = up[i];
+               wp[i] = (low_limb >> sh_1) | (high_limb << sh_2);
+               low_limb = high_limb;
+       }
+       wp[i] = low_limb >> sh_1;
+
+       return retval;
+}
diff --git a/lib/mpi/generic_mpih-sub1.c b/lib/mpi/generic_mpih-sub1.c
new file mode 100644 (file)
index 0000000..5d98ab7
--- /dev/null
@@ -0,0 +1,60 @@
+/* mpihelp-add_2.c  -  MPI helper functions
+ * Copyright (C) 1994, 1996, 1997, 1998, 2001 Free Software Foundation, Inc.
+ *
+ * This file is part of GnuPG.
+ *
+ * GnuPG is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation; either version 2 of the License, or
+ * (at your option) any later version.
+ *
+ * GnuPG is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software
+ * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA
+ *
+ * Note: This code is heavily based on the GNU MP Library.
+ *      Actually it's the same code with only minor changes in the
+ *      way the data is stored; this is to support the abstraction
+ *      of an optional secure memory allocation which may be used
+ *      to avoid revealing of sensitive data due to paging etc.
+ *      The GNU MP Library itself is published under the LGPL;
+ *      however I decided to publish this code under the plain GPL.
+ */
+
+#include "mpi-internal.h"
+#include "longlong.h"
+
+mpi_limb_t
+mpihelp_sub_n(mpi_ptr_t res_ptr, mpi_ptr_t s1_ptr,
+             mpi_ptr_t s2_ptr, mpi_size_t size)
+{
+       mpi_limb_t x, y, cy;
+       mpi_size_t j;
+
+       /* The loop counter and index J goes from -SIZE to -1.  This way
+          the loop becomes faster.  */
+       j = -size;
+
+       /* Offset the base pointers to compensate for the negative indices.  */
+       s1_ptr -= j;
+       s2_ptr -= j;
+       res_ptr -= j;
+
+       cy = 0;
+       do {
+               y = s2_ptr[j];
+               x = s1_ptr[j];
+               y += cy;        /* add previous carry to subtrahend */
+               cy = y < cy;    /* get out carry from that addition */
+               y = x - y;      /* main subtract */
+               cy += y > x;    /* get out carry from the subtract, combine */
+               res_ptr[j] = y;
+       } while (++j);
+
+       return cy;
+}
diff --git a/lib/mpi/mpi-bit.c b/lib/mpi/mpi-bit.c
new file mode 100644 (file)
index 0000000..854c9c6
--- /dev/null
@@ -0,0 +1,236 @@
+/* mpi-bit.c  -  MPI bit level fucntions
+ * Copyright (C) 1998, 1999 Free Software Foundation, Inc.
+ *
+ * This file is part of GnuPG.
+ *
+ * GnuPG is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation; either version 2 of the License, or
+ * (at your option) any later version.
+ *
+ * GnuPG is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software
+ * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA
+ */
+
+#include "mpi-internal.h"
+#include "longlong.h"
+
+const unsigned char __clz_tab[] = {
+       0, 1, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4, 5, 5, 5, 5, 5, 5, 5, 5,
+           5, 5, 5, 5, 5, 5, 5, 5,
+       6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
+           6, 6, 6, 6, 6, 6, 6, 6,
+       7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
+           7, 7, 7, 7, 7, 7, 7, 7,
+       7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
+           7, 7, 7, 7, 7, 7, 7, 7,
+       8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
+           8, 8, 8, 8, 8, 8, 8, 8,
+       8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
+           8, 8, 8, 8, 8, 8, 8, 8,
+       8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
+           8, 8, 8, 8, 8, 8, 8, 8,
+       8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
+           8, 8, 8, 8, 8, 8, 8, 8,
+};
+
+#define A_LIMB_1 ((mpi_limb_t) 1)
+
+/****************
+ * Sometimes we have MSL (most significant limbs) which are 0;
+ * this is for some reasons not good, so this function removes them.
+ */
+void mpi_normalize(MPI a)
+{
+       for (; a->nlimbs && !a->d[a->nlimbs - 1]; a->nlimbs--)
+               ;
+}
+
+/****************
+ * Return the number of bits in A.
+ */
+unsigned mpi_get_nbits(MPI a)
+{
+       unsigned n;
+
+       mpi_normalize(a);
+
+       if (a->nlimbs) {
+               mpi_limb_t alimb = a->d[a->nlimbs - 1];
+               if (alimb)
+                       count_leading_zeros(n, alimb);
+               else
+                       n = BITS_PER_MPI_LIMB;
+               n = BITS_PER_MPI_LIMB - n + (a->nlimbs - 1) * BITS_PER_MPI_LIMB;
+       } else
+               n = 0;
+       return n;
+}
+EXPORT_SYMBOL_GPL(mpi_get_nbits);
+
+/****************
+ * Test whether bit N is set.
+ */
+int mpi_test_bit(MPI a, unsigned n)
+{
+       unsigned limbno, bitno;
+       mpi_limb_t limb;
+
+       limbno = n / BITS_PER_MPI_LIMB;
+       bitno = n % BITS_PER_MPI_LIMB;
+
+       if (limbno >= a->nlimbs)
+               return 0;       /* too far left: this is a 0 */
+       limb = a->d[limbno];
+       return (limb & (A_LIMB_1 << bitno)) ? 1 : 0;
+}
+
+/****************
+ * Set bit N of A.
+ */
+int mpi_set_bit(MPI a, unsigned n)
+{
+       unsigned limbno, bitno;
+
+       limbno = n / BITS_PER_MPI_LIMB;
+       bitno = n % BITS_PER_MPI_LIMB;
+
+       if (limbno >= a->nlimbs) {      /* resize */
+               if (a->alloced >= limbno)
+                       if (mpi_resize(a, limbno + 1) < 0)
+                               return -ENOMEM;
+               a->nlimbs = limbno + 1;
+       }
+       a->d[limbno] |= (A_LIMB_1 << bitno);
+       return 0;
+}
+
+/****************
+ * Set bit N of A. and clear all bits above
+ */
+int mpi_set_highbit(MPI a, unsigned n)
+{
+       unsigned limbno, bitno;
+
+       limbno = n / BITS_PER_MPI_LIMB;
+       bitno = n % BITS_PER_MPI_LIMB;
+
+       if (limbno >= a->nlimbs) {      /* resize */
+               if (a->alloced >= limbno)
+                       if (mpi_resize(a, limbno + 1) < 0)
+                               return -ENOMEM;
+               a->nlimbs = limbno + 1;
+       }
+       a->d[limbno] |= (A_LIMB_1 << bitno);
+       for (bitno++; bitno < BITS_PER_MPI_LIMB; bitno++)
+               a->d[limbno] &= ~(A_LIMB_1 << bitno);
+       a->nlimbs = limbno + 1;
+       return 0;
+}
+
+/****************
+ * clear bit N of A and all bits above
+ */
+void mpi_clear_highbit(MPI a, unsigned n)
+{
+       unsigned limbno, bitno;
+
+       limbno = n / BITS_PER_MPI_LIMB;
+       bitno = n % BITS_PER_MPI_LIMB;
+
+       if (limbno >= a->nlimbs)
+               return;         /* not allocated, so need to clear bits :-) */
+
+       for (; bitno < BITS_PER_MPI_LIMB; bitno++)
+               a->d[limbno] &= ~(A_LIMB_1 << bitno);
+       a->nlimbs = limbno + 1;
+}
+
+/****************
+ * Clear bit N of A.
+ */
+void mpi_clear_bit(MPI a, unsigned n)
+{
+       unsigned limbno, bitno;
+
+       limbno = n / BITS_PER_MPI_LIMB;
+       bitno = n % BITS_PER_MPI_LIMB;
+
+       if (limbno >= a->nlimbs)
+               return;         /* don't need to clear this bit, it's to far to left */
+       a->d[limbno] &= ~(A_LIMB_1 << bitno);
+}
+
+/****************
+ * Shift A by N bits to the right
+ * FIXME: should use alloc_limb if X and A are same.
+ */
+int mpi_rshift(MPI x, MPI a, unsigned n)
+{
+       mpi_ptr_t xp;
+       mpi_size_t xsize;
+
+       xsize = a->nlimbs;
+       x->sign = a->sign;
+       if (RESIZE_IF_NEEDED(x, (size_t) xsize) < 0)
+               return -ENOMEM;
+       xp = x->d;
+
+       if (xsize) {
+               mpihelp_rshift(xp, a->d, xsize, n);
+               MPN_NORMALIZE(xp, xsize);
+       }
+       x->nlimbs = xsize;
+       return 0;
+}
+
+/****************
+ * Shift A by COUNT limbs to the left
+ * This is used only within the MPI library
+ */
+int mpi_lshift_limbs(MPI a, unsigned int count)
+{
+       mpi_ptr_t ap = a->d;
+       int n = a->nlimbs;
+       int i;
+
+       if (!count || !n)
+               return 0;
+
+       if (RESIZE_IF_NEEDED(a, n + count) < 0)
+               return -ENOMEM;
+
+       for (i = n - 1; i >= 0; i--)
+               ap[i + count] = ap[i];
+       for (i = 0; i < count; i++)
+               ap[i] = 0;
+       a->nlimbs += count;
+       return 0;
+}
+
+/****************
+ * Shift A by COUNT limbs to the right
+ * This is used only within the MPI library
+ */
+void mpi_rshift_limbs(MPI a, unsigned int count)
+{
+       mpi_ptr_t ap = a->d;
+       mpi_size_t n = a->nlimbs;
+       unsigned int i;
+
+       if (count >= n) {
+               a->nlimbs = 0;
+               return;
+       }
+
+       for (i = 0; i < n - count; i++)
+               ap[i] = ap[i + count];
+       ap[i] = 0;
+       a->nlimbs -= count;
+}
diff --git a/lib/mpi/mpi-pow.c b/lib/mpi/mpi-pow.c
new file mode 100644 (file)
index 0000000..b04a3cf
--- /dev/null
@@ -0,0 +1,323 @@
+/* mpi-pow.c  -  MPI functions
+ *     Copyright (C) 1994, 1996, 1998, 2000 Free Software Foundation, Inc.
+ *
+ * This file is part of GnuPG.
+ *
+ * GnuPG is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation; either version 2 of the License, or
+ * (at your option) any later version.
+ *
+ * GnuPG is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software
+ * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA
+ *
+ * Note: This code is heavily based on the GNU MP Library.
+ *      Actually it's the same code with only minor changes in the
+ *      way the data is stored; this is to support the abstraction
+ *      of an optional secure memory allocation which may be used
+ *      to avoid revealing of sensitive data due to paging etc.
+ *      The GNU MP Library itself is published under the LGPL;
+ *      however I decided to publish this code under the plain GPL.
+ */
+
+#include <linux/string.h>
+#include "mpi-internal.h"
+#include "longlong.h"
+
+/****************
+ * RES = BASE ^ EXP mod MOD
+ */
+int mpi_powm(MPI res, MPI base, MPI exp, MPI mod)
+{
+       mpi_ptr_t mp_marker = NULL, bp_marker = NULL, ep_marker = NULL;
+       mpi_ptr_t xp_marker = NULL;
+       mpi_ptr_t tspace = NULL;
+       mpi_ptr_t rp, ep, mp, bp;
+       mpi_size_t esize, msize, bsize, rsize;
+       int esign, msign, bsign, rsign;
+       mpi_size_t size;
+       int mod_shift_cnt;
+       int negative_result;
+       int assign_rp = 0;
+       mpi_size_t tsize = 0;   /* to avoid compiler warning */
+       /* fixme: we should check that the warning is void */
+       int rc = -ENOMEM;
+
+       esize = exp->nlimbs;
+       msize = mod->nlimbs;
+       size = 2 * msize;
+       esign = exp->sign;
+       msign = mod->sign;
+
+       rp = res->d;
+       ep = exp->d;
+
+       if (!msize)
+               msize = 1 / msize;      /* provoke a signal */
+
+       if (!esize) {
+               /* Exponent is zero, result is 1 mod MOD, i.e., 1 or 0
+                * depending on if MOD equals 1.  */
+               rp[0] = 1;
+               res->nlimbs = (msize == 1 && mod->d[0] == 1) ? 0 : 1;
+               res->sign = 0;
+               goto leave;
+       }
+
+       /* Normalize MOD (i.e. make its most significant bit set) as required by
+        * mpn_divrem.  This will make the intermediate values in the calculation
+        * slightly larger, but the correct result is obtained after a final
+        * reduction using the original MOD value.  */
+       mp = mp_marker = mpi_alloc_limb_space(msize);
+       if (!mp)
+               goto enomem;
+       count_leading_zeros(mod_shift_cnt, mod->d[msize - 1]);
+       if (mod_shift_cnt)
+               mpihelp_lshift(mp, mod->d, msize, mod_shift_cnt);
+       else
+               MPN_COPY(mp, mod->d, msize);
+
+       bsize = base->nlimbs;
+       bsign = base->sign;
+       if (bsize > msize) {    /* The base is larger than the module. Reduce it. */
+               /* Allocate (BSIZE + 1) with space for remainder and quotient.
+                * (The quotient is (bsize - msize + 1) limbs.)  */
+               bp = bp_marker = mpi_alloc_limb_space(bsize + 1);
+               if (!bp)
+                       goto enomem;
+               MPN_COPY(bp, base->d, bsize);
+               /* We don't care about the quotient, store it above the remainder,
+                * at BP + MSIZE.  */
+               mpihelp_divrem(bp + msize, 0, bp, bsize, mp, msize);
+               bsize = msize;
+               /* Canonicalize the base, since we are going to multiply with it
+                * quite a few times.  */
+               MPN_NORMALIZE(bp, bsize);
+       } else
+               bp = base->d;
+
+       if (!bsize) {
+               res->nlimbs = 0;
+               res->sign = 0;
+               goto leave;
+       }
+
+       if (res->alloced < size) {
+               /* We have to allocate more space for RES.  If any of the input
+                * parameters are identical to RES, defer deallocation of the old
+                * space.  */
+               if (rp == ep || rp == mp || rp == bp) {
+                       rp = mpi_alloc_limb_space(size);
+                       if (!rp)
+                               goto enomem;
+                       assign_rp = 1;
+               } else {
+                       if (mpi_resize(res, size) < 0)
+                               goto enomem;
+                       rp = res->d;
+               }
+       } else {                /* Make BASE, EXP and MOD not overlap with RES.  */
+               if (rp == bp) {
+                       /* RES and BASE are identical.  Allocate temp. space for BASE.  */
+                       BUG_ON(bp_marker);
+                       bp = bp_marker = mpi_alloc_limb_space(bsize);
+                       if (!bp)
+                               goto enomem;
+                       MPN_COPY(bp, rp, bsize);
+               }
+               if (rp == ep) {
+                       /* RES and EXP are identical.  Allocate temp. space for EXP.  */
+                       ep = ep_marker = mpi_alloc_limb_space(esize);
+                       if (!ep)
+                               goto enomem;
+                       MPN_COPY(ep, rp, esize);
+               }
+               if (rp == mp) {
+                       /* RES and MOD are identical.  Allocate temporary space for MOD. */
+                       BUG_ON(mp_marker);
+                       mp = mp_marker = mpi_alloc_limb_space(msize);
+                       if (!mp)
+                               goto enomem;
+                       MPN_COPY(mp, rp, msize);
+               }
+       }
+
+       MPN_COPY(rp, bp, bsize);
+       rsize = bsize;
+       rsign = bsign;
+
+       {
+               mpi_size_t i;
+               mpi_ptr_t xp;
+               int c;
+               mpi_limb_t e;
+               mpi_limb_t carry_limb;
+               struct karatsuba_ctx karactx;
+
+               xp = xp_marker = mpi_alloc_limb_space(2 * (msize + 1));
+               if (!xp)
+                       goto enomem;
+
+               memset(&karactx, 0, sizeof karactx);
+               negative_result = (ep[0] & 1) && base->sign;
+
+               i = esize - 1;
+               e = ep[i];
+               count_leading_zeros(c, e);
+               e = (e << c) << 1;      /* shift the exp bits to the left, lose msb */
+               c = BITS_PER_MPI_LIMB - 1 - c;
+
+               /* Main loop.
+                *
+                * Make the result be pointed to alternately by XP and RP.  This
+                * helps us avoid block copying, which would otherwise be necessary
+                * with the overlap restrictions of mpihelp_divmod. With 50% probability
+                * the result after this loop will be in the area originally pointed
+                * by RP (==RES->d), and with 50% probability in the area originally
+                * pointed to by XP.
+                */
+
+               for (;;) {
+                       while (c) {
+                               mpi_ptr_t tp;
+                               mpi_size_t xsize;
+
+                               /*if (mpihelp_mul_n(xp, rp, rp, rsize) < 0) goto enomem */
+                               if (rsize < KARATSUBA_THRESHOLD)
+                                       mpih_sqr_n_basecase(xp, rp, rsize);
+                               else {
+                                       if (!tspace) {
+                                               tsize = 2 * rsize;
+                                               tspace =
+                                                   mpi_alloc_limb_space(tsize);
+                                               if (!tspace)
+                                                       goto enomem;
+                                       } else if (tsize < (2 * rsize)) {
+                                               mpi_free_limb_space(tspace);
+                                               tsize = 2 * rsize;
+                                               tspace =
+                                                   mpi_alloc_limb_space(tsize);
+                                               if (!tspace)
+                                                       goto enomem;
+                                       }
+                                       mpih_sqr_n(xp, rp, rsize, tspace);
+                               }
+
+                               xsize = 2 * rsize;
+                               if (xsize > msize) {
+                                       mpihelp_divrem(xp + msize, 0, xp, xsize,
+                                                      mp, msize);
+                                       xsize = msize;
+                               }
+
+                               tp = rp;
+                               rp = xp;
+                               xp = tp;
+                               rsize = xsize;
+
+                               if ((mpi_limb_signed_t) e < 0) {
+                                       /*mpihelp_mul( xp, rp, rsize, bp, bsize ); */
+                                       if (bsize < KARATSUBA_THRESHOLD) {
+                                               mpi_limb_t tmp;
+                                               if (mpihelp_mul
+                                                   (xp, rp, rsize, bp, bsize,
+                                                    &tmp) < 0)
+                                                       goto enomem;
+                                       } else {
+                                               if (mpihelp_mul_karatsuba_case
+                                                   (xp, rp, rsize, bp, bsize,
+                                                    &karactx) < 0)
+                                                       goto enomem;
+                                       }
+
+                                       xsize = rsize + bsize;
+                                       if (xsize > msize) {
+                                               mpihelp_divrem(xp + msize, 0,
+                                                              xp, xsize, mp,
+                                                              msize);
+                                               xsize = msize;
+                                       }
+
+                                       tp = rp;
+                                       rp = xp;
+                                       xp = tp;
+                                       rsize = xsize;
+                               }
+                               e <<= 1;
+                               c--;
+                       }
+
+                       i--;
+                       if (i < 0)
+                               break;
+                       e = ep[i];
+                       c = BITS_PER_MPI_LIMB;
+               }
+
+               /* We shifted MOD, the modulo reduction argument, left MOD_SHIFT_CNT
+                * steps.  Adjust the result by reducing it with the original MOD.
+                *
+                * Also make sure the result is put in RES->d (where it already
+                * might be, see above).
+                */
+               if (mod_shift_cnt) {
+                       carry_limb =
+                           mpihelp_lshift(res->d, rp, rsize, mod_shift_cnt);
+                       rp = res->d;
+                       if (carry_limb) {
+                               rp[rsize] = carry_limb;
+                               rsize++;
+                       }
+               } else {
+                       MPN_COPY(res->d, rp, rsize);
+                       rp = res->d;
+               }
+
+               if (rsize >= msize) {
+                       mpihelp_divrem(rp + msize, 0, rp, rsize, mp, msize);
+                       rsize = msize;
+               }
+
+               /* Remove any leading zero words from the result.  */
+               if (mod_shift_cnt)
+                       mpihelp_rshift(rp, rp, rsize, mod_shift_cnt);
+               MPN_NORMALIZE(rp, rsize);
+
+               mpihelp_release_karatsuba_ctx(&karactx);
+       }
+
+       if (negative_result && rsize) {
+               if (mod_shift_cnt)
+                       mpihelp_rshift(mp, mp, msize, mod_shift_cnt);
+               mpihelp_sub(rp, mp, msize, rp, rsize);
+               rsize = msize;
+               rsign = msign;
+               MPN_NORMALIZE(rp, rsize);
+       }
+       res->nlimbs = rsize;
+       res->sign = rsign;
+
+leave:
+       rc = 0;
+enomem:
+       if (assign_rp)
+               mpi_assign_limb_space(res, rp, size);
+       if (mp_marker)
+               mpi_free_limb_space(mp_marker);
+       if (bp_marker)
+               mpi_free_limb_space(bp_marker);
+       if (ep_marker)
+               mpi_free_limb_space(ep_marker);
+       if (xp_marker)
+               mpi_free_limb_space(xp_marker);
+       if (tspace)
+               mpi_free_limb_space(tspace);
+       return rc;
+}
+EXPORT_SYMBOL_GPL(mpi_powm);
diff --git a/lib/mpi/mpicoder.c b/lib/mpi/mpicoder.c
new file mode 100644 (file)
index 0000000..fe84bb9
--- /dev/null
@@ -0,0 +1,365 @@
+/* mpicoder.c  -  Coder for the external representation of MPIs
+ * Copyright (C) 1998, 1999 Free Software Foundation, Inc.
+ *
+ * This file is part of GnuPG.
+ *
+ * GnuPG is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation; either version 2 of the License, or
+ * (at your option) any later version.
+ *
+ * GnuPG is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software
+ * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA
+ */
+
+#include "mpi-internal.h"
+
+#define DIM(v) (sizeof(v)/sizeof((v)[0]))
+#define MAX_EXTERN_MPI_BITS 16384
+
+static uint8_t asn[15] =       /* Object ID is 1.3.14.3.2.26 */
+{ 0x30, 0x21, 0x30, 0x09, 0x06, 0x05, 0x2b, 0x0e, 0x03,
+       0x02, 0x1a, 0x05, 0x00, 0x04, 0x14
+};
+
+MPI do_encode_md(const void *sha_buffer, unsigned nbits)
+{
+       int nframe = (nbits + 7) / 8;
+       uint8_t *frame, *fr_pt;
+       int i = 0, n;
+       size_t asnlen = DIM(asn);
+       MPI a = MPI_NULL;
+
+       if (SHA1_DIGEST_LENGTH + asnlen + 4 > nframe)
+               pr_info("MPI: can't encode a %d bit MD into a %d bits frame\n",
+                      (int)(SHA1_DIGEST_LENGTH * 8), (int)nbits);
+
+       /* We encode the MD in this way:
+        *
+        *       0  A PAD(n bytes)   0  ASN(asnlen bytes)  MD(len bytes)
+        *
+        * PAD consists of FF bytes.
+        */
+       frame = kmalloc(nframe, GFP_KERNEL);
+       if (!frame)
+               return MPI_NULL;
+       n = 0;
+       frame[n++] = 0;
+       frame[n++] = 1;         /* block type */
+       i = nframe - SHA1_DIGEST_LENGTH - asnlen - 3;
+
+       if (i <= 1) {
+               pr_info("MPI: message digest encoding failed\n");
+               kfree(frame);
+               return a;
+       }
+
+       memset(frame + n, 0xff, i);
+       n += i;
+       frame[n++] = 0;
+       memcpy(frame + n, &asn, asnlen);
+       n += asnlen;
+       memcpy(frame + n, sha_buffer, SHA1_DIGEST_LENGTH);
+       n += SHA1_DIGEST_LENGTH;
+
+       i = nframe;
+       fr_pt = frame;
+
+       if (n != nframe) {
+               printk
+                   ("MPI: message digest encoding failed, frame length is wrong\n");
+               kfree(frame);
+               return a;
+       }
+
+       a = mpi_alloc((nframe + BYTES_PER_MPI_LIMB - 1) / BYTES_PER_MPI_LIMB);
+       mpi_set_buffer(a, frame, nframe, 0);
+       kfree(frame);
+
+       return a;
+}
+
+MPI mpi_read_from_buffer(const void *xbuffer, unsigned *ret_nread)
+{
+       const uint8_t *buffer = xbuffer;
+       int i, j;
+       unsigned nbits, nbytes, nlimbs, nread = 0;
+       mpi_limb_t a;
+       MPI val = MPI_NULL;
+
+       if (*ret_nread < 2)
+               goto leave;
+       nbits = buffer[0] << 8 | buffer[1];
+
+       if (nbits > MAX_EXTERN_MPI_BITS) {
+               pr_info("MPI: mpi too large (%u bits)\n", nbits);
+               goto leave;
+       }
+       buffer += 2;
+       nread = 2;
+
+       nbytes = (nbits + 7) / 8;
+       nlimbs = (nbytes + BYTES_PER_MPI_LIMB - 1) / BYTES_PER_MPI_LIMB;
+       val = mpi_alloc(nlimbs);
+       if (!val)
+               return MPI_NULL;
+       i = BYTES_PER_MPI_LIMB - nbytes % BYTES_PER_MPI_LIMB;
+       i %= BYTES_PER_MPI_LIMB;
+       val->nbits = nbits;
+       j = val->nlimbs = nlimbs;
+       val->sign = 0;
+       for (; j > 0; j--) {
+               a = 0;
+               for (; i < BYTES_PER_MPI_LIMB; i++) {
+                       if (++nread > *ret_nread) {
+                               printk
+                                   ("MPI: mpi larger than buffer nread=%d ret_nread=%d\n",
+                                    nread, *ret_nread);
+                               goto leave;
+                       }
+                       a <<= 8;
+                       a |= *buffer++;
+               }
+               i = 0;
+               val->d[j - 1] = a;
+       }
+
+leave:
+       *ret_nread = nread;
+       return val;
+}
+EXPORT_SYMBOL_GPL(mpi_read_from_buffer);
+
+/****************
+ * Make an mpi from a character string.
+ */
+int mpi_fromstr(MPI val, const char *str)
+{
+       int hexmode = 0, sign = 0, prepend_zero = 0, i, j, c, c1, c2;
+       unsigned nbits, nbytes, nlimbs;
+       mpi_limb_t a;
+
+       if (*str == '-') {
+               sign = 1;
+               str++;
+       }
+       if (*str == '0' && str[1] == 'x')
+               hexmode = 1;
+       else
+               return -EINVAL; /* other bases are not yet supported */
+       str += 2;
+
+       nbits = strlen(str) * 4;
+       if (nbits % 8)
+               prepend_zero = 1;
+       nbytes = (nbits + 7) / 8;
+       nlimbs = (nbytes + BYTES_PER_MPI_LIMB - 1) / BYTES_PER_MPI_LIMB;
+       if (val->alloced < nlimbs)
+               if (!mpi_resize(val, nlimbs))
+                       return -ENOMEM;
+       i = BYTES_PER_MPI_LIMB - nbytes % BYTES_PER_MPI_LIMB;
+       i %= BYTES_PER_MPI_LIMB;
+       j = val->nlimbs = nlimbs;
+       val->sign = sign;
+       for (; j > 0; j--) {
+               a = 0;
+               for (; i < BYTES_PER_MPI_LIMB; i++) {
+                       if (prepend_zero) {
+                               c1 = '0';
+                               prepend_zero = 0;
+                       } else
+                               c1 = *str++;
+                       assert(c1);
+                       c2 = *str++;
+                       assert(c2);
+                       if (c1 >= '0' && c1 <= '9')
+                               c = c1 - '0';
+                       else if (c1 >= 'a' && c1 <= 'f')
+                               c = c1 - 'a' + 10;
+                       else if (c1 >= 'A' && c1 <= 'F')
+                               c = c1 - 'A' + 10;
+                       else {
+                               mpi_clear(val);
+                               return 1;
+                       }
+                       c <<= 4;
+                       if (c2 >= '0' && c2 <= '9')
+                               c |= c2 - '0';
+                       else if (c2 >= 'a' && c2 <= 'f')
+                               c |= c2 - 'a' + 10;
+                       else if (c2 >= 'A' && c2 <= 'F')
+                               c |= c2 - 'A' + 10;
+                       else {
+                               mpi_clear(val);
+                               return 1;
+                       }
+                       a <<= 8;
+                       a |= c;
+               }
+               i = 0;
+
+               val->d[j - 1] = a;
+       }
+
+       return 0;
+}
+EXPORT_SYMBOL_GPL(mpi_fromstr);
+
+/****************
+ * Special function to get the low 8 bytes from an mpi.
+ * This can be used as a keyid; KEYID is an 2 element array.
+ * Return the low 4 bytes.
+ */
+u32 mpi_get_keyid(const MPI a, u32 *keyid)
+{
+#if BYTES_PER_MPI_LIMB == 4
+       if (keyid) {
+               keyid[0] = a->nlimbs >= 2 ? a->d[1] : 0;
+               keyid[1] = a->nlimbs >= 1 ? a->d[0] : 0;
+       }
+       return a->nlimbs >= 1 ? a->d[0] : 0;
+#elif BYTES_PER_MPI_LIMB == 8
+       if (keyid) {
+               keyid[0] = a->nlimbs ? (u32) (a->d[0] >> 32) : 0;
+               keyid[1] = a->nlimbs ? (u32) (a->d[0] & 0xffffffff) : 0;
+       }
+       return a->nlimbs ? (u32) (a->d[0] & 0xffffffff) : 0;
+#else
+#error Make this function work with other LIMB sizes
+#endif
+}
+
+/****************
+ * Return an allocated buffer with the MPI (msb first).
+ * NBYTES receives the length of this buffer. Caller must free the
+ * return string (This function does return a 0 byte buffer with NBYTES
+ * set to zero if the value of A is zero. If sign is not NULL, it will
+ * be set to the sign of the A.
+ */
+void *mpi_get_buffer(MPI a, unsigned *nbytes, int *sign)
+{
+       uint8_t *p, *buffer;
+       mpi_limb_t alimb;
+       int i;
+       unsigned int n;
+
+       if (sign)
+               *sign = a->sign;
+       *nbytes = n = a->nlimbs * BYTES_PER_MPI_LIMB;
+       if (!n)
+               n++;            /* avoid zero length allocation */
+       p = buffer = kmalloc(n, GFP_KERNEL);
+
+       for (i = a->nlimbs - 1; i >= 0; i--) {
+               alimb = a->d[i];
+#if BYTES_PER_MPI_LIMB == 4
+               *p++ = alimb >> 24;
+               *p++ = alimb >> 16;
+               *p++ = alimb >> 8;
+               *p++ = alimb;
+#elif BYTES_PER_MPI_LIMB == 8
+               *p++ = alimb >> 56;
+               *p++ = alimb >> 48;
+               *p++ = alimb >> 40;
+               *p++ = alimb >> 32;
+               *p++ = alimb >> 24;
+               *p++ = alimb >> 16;
+               *p++ = alimb >> 8;
+               *p++ = alimb;
+#else
+#error please implement for this limb size.
+#endif
+       }
+
+       /* this is sub-optimal but we need to do the shift operation
+        * because the caller has to free the returned buffer */
+       for (p = buffer; !*p && *nbytes; p++, --*nbytes)
+               ;
+       if (p != buffer)
+               memmove(buffer, p, *nbytes);
+
+       return buffer;
+}
+EXPORT_SYMBOL_GPL(mpi_get_buffer);
+
+/****************
+ * Use BUFFER to update MPI.
+ */
+int mpi_set_buffer(MPI a, const void *xbuffer, unsigned nbytes, int sign)
+{
+       const uint8_t *buffer = xbuffer, *p;
+       mpi_limb_t alimb;
+       int nlimbs;
+       int i;
+
+       nlimbs = (nbytes + BYTES_PER_MPI_LIMB - 1) / BYTES_PER_MPI_LIMB;
+       if (RESIZE_IF_NEEDED(a, nlimbs) < 0)
+               return -ENOMEM;
+       a->sign = sign;
+
+       for (i = 0, p = buffer + nbytes - 1; p >= buffer + BYTES_PER_MPI_LIMB;) {
+#if BYTES_PER_MPI_LIMB == 4
+               alimb = (mpi_limb_t) *p--;
+               alimb |= (mpi_limb_t) *p-- << 8;
+               alimb |= (mpi_limb_t) *p-- << 16;
+               alimb |= (mpi_limb_t) *p-- << 24;
+#elif BYTES_PER_MPI_LIMB == 8
+               alimb = (mpi_limb_t) *p--;
+               alimb |= (mpi_limb_t) *p-- << 8;
+               alimb |= (mpi_limb_t) *p-- << 16;
+               alimb |= (mpi_limb_t) *p-- << 24;
+               alimb |= (mpi_limb_t) *p-- << 32;
+               alimb |= (mpi_limb_t) *p-- << 40;
+               alimb |= (mpi_limb_t) *p-- << 48;
+               alimb |= (mpi_limb_t) *p-- << 56;
+#else
+#error please implement for this limb size.
+#endif
+               a->d[i++] = alimb;
+       }
+       if (p >= buffer) {
+#if BYTES_PER_MPI_LIMB == 4
+               alimb = *p--;
+               if (p >= buffer)
+                       alimb |= (mpi_limb_t) *p-- << 8;
+               if (p >= buffer)
+                       alimb |= (mpi_limb_t) *p-- << 16;
+               if (p >= buffer)
+                       alimb |= (mpi_limb_t) *p-- << 24;
+#elif BYTES_PER_MPI_LIMB == 8
+               alimb = (mpi_limb_t) *p--;
+               if (p >= buffer)
+                       alimb |= (mpi_limb_t) *p-- << 8;
+               if (p >= buffer)
+                       alimb |= (mpi_limb_t) *p-- << 16;
+               if (p >= buffer)
+                       alimb |= (mpi_limb_t) *p-- << 24;
+               if (p >= buffer)
+                       alimb |= (mpi_limb_t) *p-- << 32;
+               if (p >= buffer)
+                       alimb |= (mpi_limb_t) *p-- << 40;
+               if (p >= buffer)
+                       alimb |= (mpi_limb_t) *p-- << 48;
+               if (p >= buffer)
+                       alimb |= (mpi_limb_t) *p-- << 56;
+#else
+#error please implement for this limb size.
+#endif
+               a->d[i++] = alimb;
+       }
+       a->nlimbs = i;
+
+       if (i != nlimbs) {
+               pr_emerg("MPI: mpi_set_buffer: Assertion failed (%d != %d)", i,
+                      nlimbs);
+               BUG();
+       }
+       return 0;
+}
+EXPORT_SYMBOL_GPL(mpi_set_buffer);
diff --git a/lib/mpi/mpih-cmp.c b/lib/mpi/mpih-cmp.c
new file mode 100644 (file)
index 0000000..b2fd396
--- /dev/null
@@ -0,0 +1,56 @@
+/* mpihelp-sub.c  -  MPI helper functions
+ *     Copyright (C) 1994, 1996 Free Software Foundation, Inc.
+ *     Copyright (C) 1998, 1999, 2000, 2001 Free Software Foundation, Inc.
+ *
+ * This file is part of GnuPG.
+ *
+ * GnuPG is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation; either version 2 of the License, or
+ * (at your option) any later version.
+ *
+ * GnuPG is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software
+ * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA
+ *
+ * Note: This code is heavily based on the GNU MP Library.
+ *      Actually it's the same code with only minor changes in the
+ *      way the data is stored; this is to support the abstraction
+ *      of an optional secure memory allocation which may be used
+ *      to avoid revealing of sensitive data due to paging etc.
+ *      The GNU MP Library itself is published under the LGPL;
+ *      however I decided to publish this code under the plain GPL.
+ */
+
+#include "mpi-internal.h"
+
+/****************
+ * Compare OP1_PTR/OP1_SIZE with OP2_PTR/OP2_SIZE.
+ * There are no restrictions on the relative sizes of
+ * the two arguments.
+ * Return 1 if OP1 > OP2, 0 if they are equal, and -1 if OP1 < OP2.
+ */
+int mpihelp_cmp(mpi_ptr_t op1_ptr, mpi_ptr_t op2_ptr, mpi_size_t size)
+{
+       mpi_size_t i;
+       mpi_limb_t op1_word, op2_word;
+
+       for (i = size - 1; i >= 0; i--) {
+               op1_word = op1_ptr[i];
+               op2_word = op2_ptr[i];
+               if (op1_word != op2_word)
+                       goto diff;
+       }
+       return 0;
+
+diff:
+       /* This can *not* be simplified to
+        *   op2_word - op2_word
+        * since that expression might give signed overflow.  */
+       return (op1_word > op2_word) ? 1 : -1;
+}
diff --git a/lib/mpi/mpih-div.c b/lib/mpi/mpih-div.c
new file mode 100644 (file)
index 0000000..87ede16
--- /dev/null
@@ -0,0 +1,541 @@
+/* mpihelp-div.c  -  MPI helper functions
+ *     Copyright (C) 1994, 1996 Free Software Foundation, Inc.
+ *     Copyright (C) 1998, 1999 Free Software Foundation, Inc.
+ *
+ * This file is part of GnuPG.
+ *
+ * GnuPG is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation; either version 2 of the License, or
+ * (at your option) any later version.
+ *
+ * GnuPG is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software
+ * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA
+ *
+ * Note: This code is heavily based on the GNU MP Library.
+ *      Actually it's the same code with only minor changes in the
+ *      way the data is stored; this is to support the abstraction
+ *      of an optional secure memory allocation which may be used
+ *      to avoid revealing of sensitive data due to paging etc.
+ *      The GNU MP Library itself is published under the LGPL;
+ *      however I decided to publish this code under the plain GPL.
+ */
+
+#include "mpi-internal.h"
+#include "longlong.h"
+
+#ifndef UMUL_TIME
+#define UMUL_TIME 1
+#endif
+#ifndef UDIV_TIME
+#define UDIV_TIME UMUL_TIME
+#endif
+
+/* FIXME: We should be using invert_limb (or invert_normalized_limb)
+ * here (not udiv_qrnnd).
+ */
+
+mpi_limb_t
+mpihelp_mod_1(mpi_ptr_t dividend_ptr, mpi_size_t dividend_size,
+             mpi_limb_t divisor_limb)
+{
+       mpi_size_t i;
+       mpi_limb_t n1, n0, r;
+       int dummy;
+
+       /* Botch: Should this be handled at all?  Rely on callers?  */
+       if (!dividend_size)
+               return 0;
+
+       /* If multiplication is much faster than division, and the
+        * dividend is large, pre-invert the divisor, and use
+        * only multiplications in the inner loop.
+        *
+        * This test should be read:
+        *   Does it ever help to use udiv_qrnnd_preinv?
+        *     && Does what we save compensate for the inversion overhead?
+        */
+       if (UDIV_TIME > (2 * UMUL_TIME + 6)
+           && (UDIV_TIME - (2 * UMUL_TIME + 6)) * dividend_size > UDIV_TIME) {
+               int normalization_steps;
+
+               count_leading_zeros(normalization_steps, divisor_limb);
+               if (normalization_steps) {
+                       mpi_limb_t divisor_limb_inverted;
+
+                       divisor_limb <<= normalization_steps;
+
+                       /* Compute (2**2N - 2**N * DIVISOR_LIMB) / DIVISOR_LIMB.  The
+                        * result is a (N+1)-bit approximation to 1/DIVISOR_LIMB, with the
+                        * most significant bit (with weight 2**N) implicit.
+                        *
+                        * Special case for DIVISOR_LIMB == 100...000.
+                        */
+                       if (!(divisor_limb << 1))
+                               divisor_limb_inverted = ~(mpi_limb_t) 0;
+                       else
+                               udiv_qrnnd(divisor_limb_inverted, dummy,
+                                          -divisor_limb, 0, divisor_limb);
+
+                       n1 = dividend_ptr[dividend_size - 1];
+                       r = n1 >> (BITS_PER_MPI_LIMB - normalization_steps);
+
+                       /* Possible optimization:
+                        * if (r == 0
+                        * && divisor_limb > ((n1 << normalization_steps)
+                        *                 | (dividend_ptr[dividend_size - 2] >> ...)))
+                        * ...one division less...
+                        */
+                       for (i = dividend_size - 2; i >= 0; i--) {
+                               n0 = dividend_ptr[i];
+                               UDIV_QRNND_PREINV(dummy, r, r,
+                                                 ((n1 << normalization_steps)
+                                                  | (n0 >>
+                                                     (BITS_PER_MPI_LIMB -
+                                                      normalization_steps))),
+                                                 divisor_limb,
+                                                 divisor_limb_inverted);
+                               n1 = n0;
+                       }
+                       UDIV_QRNND_PREINV(dummy, r, r,
+                                         n1 << normalization_steps,
+                                         divisor_limb, divisor_limb_inverted);
+                       return r >> normalization_steps;
+               } else {
+                       mpi_limb_t divisor_limb_inverted;
+
+                       /* Compute (2**2N - 2**N * DIVISOR_LIMB) / DIVISOR_LIMB.  The
+                        * result is a (N+1)-bit approximation to 1/DIVISOR_LIMB, with the
+                        * most significant bit (with weight 2**N) implicit.
+                        *
+                        * Special case for DIVISOR_LIMB == 100...000.
+                        */
+                       if (!(divisor_limb << 1))
+                               divisor_limb_inverted = ~(mpi_limb_t) 0;
+                       else
+                               udiv_qrnnd(divisor_limb_inverted, dummy,
+                                          -divisor_limb, 0, divisor_limb);
+
+                       i = dividend_size - 1;
+                       r = dividend_ptr[i];
+
+                       if (r >= divisor_limb)
+                               r = 0;
+                       else
+                               i--;
+
+                       for (; i >= 0; i--) {
+                               n0 = dividend_ptr[i];
+                               UDIV_QRNND_PREINV(dummy, r, r,
+                                                 n0, divisor_limb,
+                                                 divisor_limb_inverted);
+                       }
+                       return r;
+               }
+       } else {
+               if (UDIV_NEEDS_NORMALIZATION) {
+                       int normalization_steps;
+
+                       count_leading_zeros(normalization_steps, divisor_limb);
+                       if (normalization_steps) {
+                               divisor_limb <<= normalization_steps;
+
+                               n1 = dividend_ptr[dividend_size - 1];
+                               r = n1 >> (BITS_PER_MPI_LIMB -
+                                          normalization_steps);
+
+                               /* Possible optimization:
+                                * if (r == 0
+                                * && divisor_limb > ((n1 << normalization_steps)
+                                *                 | (dividend_ptr[dividend_size - 2] >> ...)))
+                                * ...one division less...
+                                */
+                               for (i = dividend_size - 2; i >= 0; i--) {
+                                       n0 = dividend_ptr[i];
+                                       udiv_qrnnd(dummy, r, r,
+                                                  ((n1 << normalization_steps)
+                                                   | (n0 >>
+                                                      (BITS_PER_MPI_LIMB -
+                                                       normalization_steps))),
+                                                  divisor_limb);
+                                       n1 = n0;
+                               }
+                               udiv_qrnnd(dummy, r, r,
+                                          n1 << normalization_steps,
+                                          divisor_limb);
+                               return r >> normalization_steps;
+                       }
+               }
+               /* No normalization needed, either because udiv_qrnnd doesn't require
+                * it, or because DIVISOR_LIMB is already normalized.  */
+               i = dividend_size - 1;
+               r = dividend_ptr[i];
+
+               if (r >= divisor_limb)
+                       r = 0;
+               else
+                       i--;
+
+               for (; i >= 0; i--) {
+                       n0 = dividend_ptr[i];
+                       udiv_qrnnd(dummy, r, r, n0, divisor_limb);
+               }
+               return r;
+       }
+}
+
+/* Divide num (NP/NSIZE) by den (DP/DSIZE) and write
+ * the NSIZE-DSIZE least significant quotient limbs at QP
+ * and the DSIZE long remainder at NP. If QEXTRA_LIMBS is
+ * non-zero, generate that many fraction bits and append them after the
+ * other quotient limbs.
+ * Return the most significant limb of the quotient, this is always 0 or 1.
+ *
+ * Preconditions:
+ * 0. NSIZE >= DSIZE.
+ * 1. The most significant bit of the divisor must be set.
+ * 2. QP must either not overlap with the input operands at all, or
+ *    QP + DSIZE >= NP must hold true. (This means that it's
+ *    possible to put the quotient in the high part of NUM, right after the
+ *    remainder in NUM.
+ * 3. NSIZE >= DSIZE, even if QEXTRA_LIMBS is non-zero.
+ */
+
+mpi_limb_t
+mpihelp_divrem(mpi_ptr_t qp, mpi_size_t qextra_limbs,
+              mpi_ptr_t np, mpi_size_t nsize, mpi_ptr_t dp, mpi_size_t dsize)
+{
+       mpi_limb_t most_significant_q_limb = 0;
+
+       switch (dsize) {
+       case 0:
+               /* We are asked to divide by zero, so go ahead and do it!  (To make
+                  the compiler not remove this statement, return the value.)  */
+               return 1 / dsize;
+
+       case 1:
+               {
+                       mpi_size_t i;
+                       mpi_limb_t n1;
+                       mpi_limb_t d;
+
+                       d = dp[0];
+                       n1 = np[nsize - 1];
+
+                       if (n1 >= d) {
+                               n1 -= d;
+                               most_significant_q_limb = 1;
+                       }
+
+                       qp += qextra_limbs;
+                       for (i = nsize - 2; i >= 0; i--)
+                               udiv_qrnnd(qp[i], n1, n1, np[i], d);
+                       qp -= qextra_limbs;
+
+                       for (i = qextra_limbs - 1; i >= 0; i--)
+                               udiv_qrnnd(qp[i], n1, n1, 0, d);
+
+                       np[0] = n1;
+               }
+               break;
+
+       case 2:
+               {
+                       mpi_size_t i;
+                       mpi_limb_t n1, n0, n2;
+                       mpi_limb_t d1, d0;
+
+                       np += nsize - 2;
+                       d1 = dp[1];
+                       d0 = dp[0];
+                       n1 = np[1];
+                       n0 = np[0];
+
+                       if (n1 >= d1 && (n1 > d1 || n0 >= d0)) {
+                               sub_ddmmss(n1, n0, n1, n0, d1, d0);
+                               most_significant_q_limb = 1;
+                       }
+
+                       for (i = qextra_limbs + nsize - 2 - 1; i >= 0; i--) {
+                               mpi_limb_t q;
+                               mpi_limb_t r;
+
+                               if (i >= qextra_limbs)
+                                       np--;
+                               else
+                                       np[0] = 0;
+
+                               if (n1 == d1) {
+                                       /* Q should be either 111..111 or 111..110.  Need special
+                                        * treatment of this rare case as normal division would
+                                        * give overflow.  */
+                                       q = ~(mpi_limb_t) 0;
+
+                                       r = n0 + d1;
+                                       if (r < d1) {   /* Carry in the addition? */
+                                               add_ssaaaa(n1, n0, r - d0,
+                                                          np[0], 0, d0);
+                                               qp[i] = q;
+                                               continue;
+                                       }
+                                       n1 = d0 - (d0 != 0 ? 1 : 0);
+                                       n0 = -d0;
+                               } else {
+                                       udiv_qrnnd(q, r, n1, n0, d1);
+                                       umul_ppmm(n1, n0, d0, q);
+                               }
+
+                               n2 = np[0];
+q_test:
+                               if (n1 > r || (n1 == r && n0 > n2)) {
+                                       /* The estimated Q was too large.  */
+                                       q--;
+                                       sub_ddmmss(n1, n0, n1, n0, 0, d0);
+                                       r += d1;
+                                       if (r >= d1)    /* If not carry, test Q again.  */
+                                               goto q_test;
+                               }
+
+                               qp[i] = q;
+                               sub_ddmmss(n1, n0, r, n2, n1, n0);
+                       }
+                       np[1] = n1;
+                       np[0] = n0;
+               }
+               break;
+
+       default:
+               {
+                       mpi_size_t i;
+                       mpi_limb_t dX, d1, n0;
+
+                       np += nsize - dsize;
+                       dX = dp[dsize - 1];
+                       d1 = dp[dsize - 2];
+                       n0 = np[dsize - 1];
+
+                       if (n0 >= dX) {
+                               if (n0 > dX
+                                   || mpihelp_cmp(np, dp, dsize - 1) >= 0) {
+                                       mpihelp_sub_n(np, np, dp, dsize);
+                                       n0 = np[dsize - 1];
+                                       most_significant_q_limb = 1;
+                               }
+                       }
+
+                       for (i = qextra_limbs + nsize - dsize - 1; i >= 0; i--) {
+                               mpi_limb_t q;
+                               mpi_limb_t n1, n2;
+                               mpi_limb_t cy_limb;
+
+                               if (i >= qextra_limbs) {
+                                       np--;
+                                       n2 = np[dsize];
+                               } else {
+                                       n2 = np[dsize - 1];
+                                       MPN_COPY_DECR(np + 1, np, dsize - 1);
+                                       np[0] = 0;
+                               }
+
+                               if (n0 == dX) {
+                                       /* This might over-estimate q, but it's probably not worth
+                                        * the extra code here to find out.  */
+                                       q = ~(mpi_limb_t) 0;
+                               } else {
+                                       mpi_limb_t r;
+
+                                       udiv_qrnnd(q, r, n0, np[dsize - 1], dX);
+                                       umul_ppmm(n1, n0, d1, q);
+
+                                       while (n1 > r
+                                              || (n1 == r
+                                                  && n0 > np[dsize - 2])) {
+                                               q--;
+                                               r += dX;
+                                               if (r < dX)     /* I.e. "carry in previous addition?" */
+                                                       break;
+                                               n1 -= n0 < d1;
+                                               n0 -= d1;
+                                       }
+                               }
+
+                               /* Possible optimization: We already have (q * n0) and (1 * n1)
+                                * after the calculation of q.  Taking advantage of that, we
+                                * could make this loop make two iterations less.  */
+                               cy_limb = mpihelp_submul_1(np, dp, dsize, q);
+
+                               if (n2 != cy_limb) {
+                                       mpihelp_add_n(np, np, dp, dsize);
+                                       q--;
+                               }
+
+                               qp[i] = q;
+                               n0 = np[dsize - 1];
+                       }
+               }
+       }
+
+       return most_significant_q_limb;
+}
+
+/****************
+ * Divide (DIVIDEND_PTR,,DIVIDEND_SIZE) by DIVISOR_LIMB.
+ * Write DIVIDEND_SIZE limbs of quotient at QUOT_PTR.
+ * Return the single-limb remainder.
+ * There are no constraints on the value of the divisor.
+ *
+ * QUOT_PTR and DIVIDEND_PTR might point to the same limb.
+ */
+
+mpi_limb_t
+mpihelp_divmod_1(mpi_ptr_t quot_ptr,
+                mpi_ptr_t dividend_ptr, mpi_size_t dividend_size,
+                mpi_limb_t divisor_limb)
+{
+       mpi_size_t i;
+       mpi_limb_t n1, n0, r;
+       int dummy;
+
+       if (!dividend_size)
+               return 0;
+
+       /* If multiplication is much faster than division, and the
+        * dividend is large, pre-invert the divisor, and use
+        * only multiplications in the inner loop.
+        *
+        * This test should be read:
+        * Does it ever help to use udiv_qrnnd_preinv?
+        * && Does what we save compensate for the inversion overhead?
+        */
+       if (UDIV_TIME > (2 * UMUL_TIME + 6)
+           && (UDIV_TIME - (2 * UMUL_TIME + 6)) * dividend_size > UDIV_TIME) {
+               int normalization_steps;
+
+               count_leading_zeros(normalization_steps, divisor_limb);
+               if (normalization_steps) {
+                       mpi_limb_t divisor_limb_inverted;
+
+                       divisor_limb <<= normalization_steps;
+
+                       /* Compute (2**2N - 2**N * DIVISOR_LIMB) / DIVISOR_LIMB.  The
+                        * result is a (N+1)-bit approximation to 1/DIVISOR_LIMB, with the
+                        * most significant bit (with weight 2**N) implicit.
+                        */
+                       /* Special case for DIVISOR_LIMB == 100...000.  */
+                       if (!(divisor_limb << 1))
+                               divisor_limb_inverted = ~(mpi_limb_t) 0;
+                       else
+                               udiv_qrnnd(divisor_limb_inverted, dummy,
+                                          -divisor_limb, 0, divisor_limb);
+
+                       n1 = dividend_ptr[dividend_size - 1];
+                       r = n1 >> (BITS_PER_MPI_LIMB - normalization_steps);
+
+                       /* Possible optimization:
+                        * if (r == 0
+                        * && divisor_limb > ((n1 << normalization_steps)
+                        *                 | (dividend_ptr[dividend_size - 2] >> ...)))
+                        * ...one division less...
+                        */
+                       for (i = dividend_size - 2; i >= 0; i--) {
+                               n0 = dividend_ptr[i];
+                               UDIV_QRNND_PREINV(quot_ptr[i + 1], r, r,
+                                                 ((n1 << normalization_steps)
+                                                  | (n0 >>
+                                                     (BITS_PER_MPI_LIMB -
+                                                      normalization_steps))),
+                                                 divisor_limb,
+                                                 divisor_limb_inverted);
+                               n1 = n0;
+                       }
+                       UDIV_QRNND_PREINV(quot_ptr[0], r, r,
+                                         n1 << normalization_steps,
+                                         divisor_limb, divisor_limb_inverted);
+                       return r >> normalization_steps;
+               } else {
+                       mpi_limb_t divisor_limb_inverted;
+
+                       /* Compute (2**2N - 2**N * DIVISOR_LIMB) / DIVISOR_LIMB.  The
+                        * result is a (N+1)-bit approximation to 1/DIVISOR_LIMB, with the
+                        * most significant bit (with weight 2**N) implicit.
+                        */
+                       /* Special case for DIVISOR_LIMB == 100...000.  */
+                       if (!(divisor_limb << 1))
+                               divisor_limb_inverted = ~(mpi_limb_t) 0;
+                       else
+                               udiv_qrnnd(divisor_limb_inverted, dummy,
+                                          -divisor_limb, 0, divisor_limb);
+
+                       i = dividend_size - 1;
+                       r = dividend_ptr[i];
+
+                       if (r >= divisor_limb)
+                               r = 0;
+                       else
+                               quot_ptr[i--] = 0;
+
+                       for (; i >= 0; i--) {
+                               n0 = dividend_ptr[i];
+                               UDIV_QRNND_PREINV(quot_ptr[i], r, r,
+                                                 n0, divisor_limb,
+                                                 divisor_limb_inverted);
+                       }
+                       return r;
+               }
+       } else {
+               if (UDIV_NEEDS_NORMALIZATION) {
+                       int normalization_steps;
+
+                       count_leading_zeros(normalization_steps, divisor_limb);
+                       if (normalization_steps) {
+                               divisor_limb <<= normalization_steps;
+
+                               n1 = dividend_ptr[dividend_size - 1];
+                               r = n1 >> (BITS_PER_MPI_LIMB -
+                                          normalization_steps);
+
+                               /* Possible optimization:
+                                * if (r == 0
+                                * && divisor_limb > ((n1 << normalization_steps)
+                                *                 | (dividend_ptr[dividend_size - 2] >> ...)))
+                                * ...one division less...
+                                */
+                               for (i = dividend_size - 2; i >= 0; i--) {
+                                       n0 = dividend_ptr[i];
+                                       udiv_qrnnd(quot_ptr[i + 1], r, r,
+                                                  ((n1 << normalization_steps)
+                                                   | (n0 >>
+                                                      (BITS_PER_MPI_LIMB -
+                                                       normalization_steps))),
+                                                  divisor_limb);
+                                       n1 = n0;
+                               }
+                               udiv_qrnnd(quot_ptr[0], r, r,
+                                          n1 << normalization_steps,
+                                          divisor_limb);
+                               return r >> normalization_steps;
+                       }
+               }
+               /* No normalization needed, either because udiv_qrnnd doesn't require
+                * it, or because DIVISOR_LIMB is already normalized.  */
+               i = dividend_size - 1;
+               r = dividend_ptr[i];
+
+               if (r >= divisor_limb)
+                       r = 0;
+               else
+                       quot_ptr[i--] = 0;
+
+               for (; i >= 0; i--) {
+                       n0 = dividend_ptr[i];
+                       udiv_qrnnd(quot_ptr[i], r, r, n0, divisor_limb);
+               }
+               return r;
+       }
+}
diff --git a/lib/mpi/mpih-mul.c b/lib/mpi/mpih-mul.c
new file mode 100644 (file)
index 0000000..c69c5ee
--- /dev/null
@@ -0,0 +1,527 @@
+/* mpihelp-mul.c  -  MPI helper functions
+ * Copyright (C) 1994, 1996, 1998, 1999,
+ *               2000 Free Software Foundation, Inc.
+ *
+ * This file is part of GnuPG.
+ *
+ * GnuPG is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation; either version 2 of the License, or
+ * (at your option) any later version.
+ *
+ * GnuPG is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software
+ * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA
+ *
+ * Note: This code is heavily based on the GNU MP Library.
+ *      Actually it's the same code with only minor changes in the
+ *      way the data is stored; this is to support the abstraction
+ *      of an optional secure memory allocation which may be used
+ *      to avoid revealing of sensitive data due to paging etc.
+ *      The GNU MP Library itself is published under the LGPL;
+ *      however I decided to publish this code under the plain GPL.
+ */
+
+#include <linux/string.h>
+#include "mpi-internal.h"
+#include "longlong.h"
+
+#define MPN_MUL_N_RECURSE(prodp, up, vp, size, tspace)         \
+       do {                                                    \
+               if ((size) < KARATSUBA_THRESHOLD)               \
+                       mul_n_basecase(prodp, up, vp, size);    \
+               else                                            \
+                       mul_n(prodp, up, vp, size, tspace);     \
+       } while (0);
+
+#define MPN_SQR_N_RECURSE(prodp, up, size, tspace)             \
+       do {                                                    \
+               if ((size) < KARATSUBA_THRESHOLD)               \
+                       mpih_sqr_n_basecase(prodp, up, size);   \
+               else                                            \
+                       mpih_sqr_n(prodp, up, size, tspace);    \
+       } while (0);
+
+/* Multiply the natural numbers u (pointed to by UP) and v (pointed to by VP),
+ * both with SIZE limbs, and store the result at PRODP.  2 * SIZE limbs are
+ * always stored.  Return the most significant limb.
+ *
+ * Argument constraints:
+ * 1. PRODP != UP and PRODP != VP, i.e. the destination
+ *    must be distinct from the multiplier and the multiplicand.
+ *
+ *
+ * Handle simple cases with traditional multiplication.
+ *
+ * This is the most critical code of multiplication.  All multiplies rely
+ * on this, both small and huge.  Small ones arrive here immediately.  Huge
+ * ones arrive here as this is the base case for Karatsuba's recursive
+ * algorithm below.
+ */
+
+static mpi_limb_t
+mul_n_basecase(mpi_ptr_t prodp, mpi_ptr_t up, mpi_ptr_t vp, mpi_size_t size)
+{
+       mpi_size_t i;
+       mpi_limb_t cy;
+       mpi_limb_t v_limb;
+
+       /* Multiply by the first limb in V separately, as the result can be
+        * stored (not added) to PROD.  We also avoid a loop for zeroing.  */
+       v_limb = vp[0];
+       if (v_limb <= 1) {
+               if (v_limb == 1)
+                       MPN_COPY(prodp, up, size);
+               else
+                       MPN_ZERO(prodp, size);
+               cy = 0;
+       } else
+               cy = mpihelp_mul_1(prodp, up, size, v_limb);
+
+       prodp[size] = cy;
+       prodp++;
+
+       /* For each iteration in the outer loop, multiply one limb from
+        * U with one limb from V, and add it to PROD.  */
+       for (i = 1; i < size; i++) {
+               v_limb = vp[i];
+               if (v_limb <= 1) {
+                       cy = 0;
+                       if (v_limb == 1)
+                               cy = mpihelp_add_n(prodp, prodp, up, size);
+               } else
+                       cy = mpihelp_addmul_1(prodp, up, size, v_limb);
+
+               prodp[size] = cy;
+               prodp++;
+       }
+
+       return cy;
+}
+
+static void
+mul_n(mpi_ptr_t prodp, mpi_ptr_t up, mpi_ptr_t vp,
+               mpi_size_t size, mpi_ptr_t tspace)
+{
+       if (size & 1) {
+               /* The size is odd, and the code below doesn't handle that.
+                * Multiply the least significant (size - 1) limbs with a recursive
+                * call, and handle the most significant limb of S1 and S2
+                * separately.
+                * A slightly faster way to do this would be to make the Karatsuba
+                * code below behave as if the size were even, and let it check for
+                * odd size in the end.  I.e., in essence move this code to the end.
+                * Doing so would save us a recursive call, and potentially make the
+                * stack grow a lot less.
+                */
+               mpi_size_t esize = size - 1;    /* even size */
+               mpi_limb_t cy_limb;
+
+               MPN_MUL_N_RECURSE(prodp, up, vp, esize, tspace);
+               cy_limb = mpihelp_addmul_1(prodp + esize, up, esize, vp[esize]);
+               prodp[esize + esize] = cy_limb;
+               cy_limb = mpihelp_addmul_1(prodp + esize, vp, size, up[esize]);
+               prodp[esize + size] = cy_limb;
+       } else {
+               /* Anatolij Alekseevich Karatsuba's divide-and-conquer algorithm.
+                *
+                * Split U in two pieces, U1 and U0, such that
+                * U = U0 + U1*(B**n),
+                * and V in V1 and V0, such that
+                * V = V0 + V1*(B**n).
+                *
+                * UV is then computed recursively using the identity
+                *
+                *        2n   n          n                     n
+                * UV = (B  + B )U V  +  B (U -U )(V -V )  +  (B + 1)U V
+                *                1 1        1  0   0  1              0 0
+                *
+                * Where B = 2**BITS_PER_MP_LIMB.
+                */
+               mpi_size_t hsize = size >> 1;
+               mpi_limb_t cy;
+               int negflg;
+
+               /* Product H.      ________________  ________________
+                *                |_____U1 x V1____||____U0 x V0_____|
+                * Put result in upper part of PROD and pass low part of TSPACE
+                * as new TSPACE.
+                */
+               MPN_MUL_N_RECURSE(prodp + size, up + hsize, vp + hsize, hsize,
+                                 tspace);
+
+               /* Product M.      ________________
+                *                |_(U1-U0)(V0-V1)_|
+                */
+               if (mpihelp_cmp(up + hsize, up, hsize) >= 0) {
+                       mpihelp_sub_n(prodp, up + hsize, up, hsize);
+                       negflg = 0;
+               } else {
+                       mpihelp_sub_n(prodp, up, up + hsize, hsize);
+                       negflg = 1;
+               }
+               if (mpihelp_cmp(vp + hsize, vp, hsize) >= 0) {
+                       mpihelp_sub_n(prodp + hsize, vp + hsize, vp, hsize);
+                       negflg ^= 1;
+               } else {
+                       mpihelp_sub_n(prodp + hsize, vp, vp + hsize, hsize);
+                       /* No change of NEGFLG.  */
+               }
+               /* Read temporary operands from low part of PROD.
+                * Put result in low part of TSPACE using upper part of TSPACE
+                * as new TSPACE.
+                */
+               MPN_MUL_N_RECURSE(tspace, prodp, prodp + hsize, hsize,
+                                 tspace + size);
+
+               /* Add/copy product H. */
+               MPN_COPY(prodp + hsize, prodp + size, hsize);
+               cy = mpihelp_add_n(prodp + size, prodp + size,
+                                  prodp + size + hsize, hsize);
+
+               /* Add product M (if NEGFLG M is a negative number) */
+               if (negflg)
+                       cy -=
+                           mpihelp_sub_n(prodp + hsize, prodp + hsize, tspace,
+                                         size);
+               else
+                       cy +=
+                           mpihelp_add_n(prodp + hsize, prodp + hsize, tspace,
+                                         size);
+
+               /* Product L.      ________________  ________________
+                *                |________________||____U0 x V0_____|
+                * Read temporary operands from low part of PROD.
+                * Put result in low part of TSPACE using upper part of TSPACE
+                * as new TSPACE.
+                */
+               MPN_MUL_N_RECURSE(tspace, up, vp, hsize, tspace + size);
+
+               /* Add/copy Product L (twice) */
+
+               cy += mpihelp_add_n(prodp + hsize, prodp + hsize, tspace, size);
+               if (cy)
+                       mpihelp_add_1(prodp + hsize + size,
+                                     prodp + hsize + size, hsize, cy);
+
+               MPN_COPY(prodp, tspace, hsize);
+               cy = mpihelp_add_n(prodp + hsize, prodp + hsize, tspace + hsize,
+                                  hsize);
+               if (cy)
+                       mpihelp_add_1(prodp + size, prodp + size, size, 1);
+       }
+}
+
+void mpih_sqr_n_basecase(mpi_ptr_t prodp, mpi_ptr_t up, mpi_size_t size)
+{
+       mpi_size_t i;
+       mpi_limb_t cy_limb;
+       mpi_limb_t v_limb;
+
+       /* Multiply by the first limb in V separately, as the result can be
+        * stored (not added) to PROD.  We also avoid a loop for zeroing.  */
+       v_limb = up[0];
+       if (v_limb <= 1) {
+               if (v_limb == 1)
+                       MPN_COPY(prodp, up, size);
+               else
+                       MPN_ZERO(prodp, size);
+               cy_limb = 0;
+       } else
+               cy_limb = mpihelp_mul_1(prodp, up, size, v_limb);
+
+       prodp[size] = cy_limb;
+       prodp++;
+
+       /* For each iteration in the outer loop, multiply one limb from
+        * U with one limb from V, and add it to PROD.  */
+       for (i = 1; i < size; i++) {
+               v_limb = up[i];
+               if (v_limb <= 1) {
+                       cy_limb = 0;
+                       if (v_limb == 1)
+                               cy_limb = mpihelp_add_n(prodp, prodp, up, size);
+               } else
+                       cy_limb = mpihelp_addmul_1(prodp, up, size, v_limb);
+
+               prodp[size] = cy_limb;
+               prodp++;
+       }
+}
+
+void
+mpih_sqr_n(mpi_ptr_t prodp, mpi_ptr_t up, mpi_size_t size, mpi_ptr_t tspace)
+{
+       if (size & 1) {
+               /* The size is odd, and the code below doesn't handle that.
+                * Multiply the least significant (size - 1) limbs with a recursive
+                * call, and handle the most significant limb of S1 and S2
+                * separately.
+                * A slightly faster way to do this would be to make the Karatsuba
+                * code below behave as if the size were even, and let it check for
+                * odd size in the end.  I.e., in essence move this code to the end.
+                * Doing so would save us a recursive call, and potentially make the
+                * stack grow a lot less.
+                */
+               mpi_size_t esize = size - 1;    /* even size */
+               mpi_limb_t cy_limb;
+
+               MPN_SQR_N_RECURSE(prodp, up, esize, tspace);
+               cy_limb = mpihelp_addmul_1(prodp + esize, up, esize, up[esize]);
+               prodp[esize + esize] = cy_limb;
+               cy_limb = mpihelp_addmul_1(prodp + esize, up, size, up[esize]);
+
+               prodp[esize + size] = cy_limb;
+       } else {
+               mpi_size_t hsize = size >> 1;
+               mpi_limb_t cy;
+
+               /* Product H.      ________________  ________________
+                *                |_____U1 x U1____||____U0 x U0_____|
+                * Put result in upper part of PROD and pass low part of TSPACE
+                * as new TSPACE.
+                */
+               MPN_SQR_N_RECURSE(prodp + size, up + hsize, hsize, tspace);
+
+               /* Product M.      ________________
+                *                |_(U1-U0)(U0-U1)_|
+                */
+               if (mpihelp_cmp(up + hsize, up, hsize) >= 0)
+                       mpihelp_sub_n(prodp, up + hsize, up, hsize);
+               else
+                       mpihelp_sub_n(prodp, up, up + hsize, hsize);
+
+               /* Read temporary operands from low part of PROD.
+                * Put result in low part of TSPACE using upper part of TSPACE
+                * as new TSPACE.  */
+               MPN_SQR_N_RECURSE(tspace, prodp, hsize, tspace + size);
+
+               /* Add/copy product H  */
+               MPN_COPY(prodp + hsize, prodp + size, hsize);
+               cy = mpihelp_add_n(prodp + size, prodp + size,
+                                  prodp + size + hsize, hsize);
+
+               /* Add product M (if NEGFLG M is a negative number).  */
+               cy -= mpihelp_sub_n(prodp + hsize, prodp + hsize, tspace, size);
+
+               /* Product L.      ________________  ________________
+                *                |________________||____U0 x U0_____|
+                * Read temporary operands from low part of PROD.
+                * Put result in low part of TSPACE using upper part of TSPACE
+                * as new TSPACE.  */
+               MPN_SQR_N_RECURSE(tspace, up, hsize, tspace + size);
+
+               /* Add/copy Product L (twice).  */
+               cy += mpihelp_add_n(prodp + hsize, prodp + hsize, tspace, size);
+               if (cy)
+                       mpihelp_add_1(prodp + hsize + size,
+                                     prodp + hsize + size, hsize, cy);
+
+               MPN_COPY(prodp, tspace, hsize);
+               cy = mpihelp_add_n(prodp + hsize, prodp + hsize, tspace + hsize,
+                                  hsize);
+               if (cy)
+                       mpihelp_add_1(prodp + size, prodp + size, size, 1);
+       }
+}
+
+/* This should be made into an inline function in gmp.h.  */
+int mpihelp_mul_n(mpi_ptr_t prodp, mpi_ptr_t up, mpi_ptr_t vp, mpi_size_t size)
+{
+       if (up == vp) {
+               if (size < KARATSUBA_THRESHOLD)
+                       mpih_sqr_n_basecase(prodp, up, size);
+               else {
+                       mpi_ptr_t tspace;
+                       tspace = mpi_alloc_limb_space(2 * size);
+                       if (!tspace)
+                               return -ENOMEM;
+                       mpih_sqr_n(prodp, up, size, tspace);
+                       mpi_free_limb_space(tspace);
+               }
+       } else {
+               if (size < KARATSUBA_THRESHOLD)
+                       mul_n_basecase(prodp, up, vp, size);
+               else {
+                       mpi_ptr_t tspace;
+                       tspace = mpi_alloc_limb_space(2 * size);
+                       if (!tspace)
+                               return -ENOMEM;
+                       mul_n(prodp, up, vp, size, tspace);
+                       mpi_free_limb_space(tspace);
+               }
+       }
+
+       return 0;
+}
+
+int
+mpihelp_mul_karatsuba_case(mpi_ptr_t prodp,
+                          mpi_ptr_t up, mpi_size_t usize,
+                          mpi_ptr_t vp, mpi_size_t vsize,
+                          struct karatsuba_ctx *ctx)
+{
+       mpi_limb_t cy;
+
+       if (!ctx->tspace || ctx->tspace_size < vsize) {
+               if (ctx->tspace)
+                       mpi_free_limb_space(ctx->tspace);
+               ctx->tspace = mpi_alloc_limb_space(2 * vsize);
+               if (!ctx->tspace)
+                       return -ENOMEM;
+               ctx->tspace_size = vsize;
+       }
+
+       MPN_MUL_N_RECURSE(prodp, up, vp, vsize, ctx->tspace);
+
+       prodp += vsize;
+       up += vsize;
+       usize -= vsize;
+       if (usize >= vsize) {
+               if (!ctx->tp || ctx->tp_size < vsize) {
+                       if (ctx->tp)
+                               mpi_free_limb_space(ctx->tp);
+                       ctx->tp = mpi_alloc_limb_space(2 * vsize);
+                       if (!ctx->tp) {
+                               if (ctx->tspace)
+                                       mpi_free_limb_space(ctx->tspace);
+                               ctx->tspace = NULL;
+                               return -ENOMEM;
+                       }
+                       ctx->tp_size = vsize;
+               }
+
+               do {
+                       MPN_MUL_N_RECURSE(ctx->tp, up, vp, vsize, ctx->tspace);
+                       cy = mpihelp_add_n(prodp, prodp, ctx->tp, vsize);
+                       mpihelp_add_1(prodp + vsize, ctx->tp + vsize, vsize,
+                                     cy);
+                       prodp += vsize;
+                       up += vsize;
+                       usize -= vsize;
+               } while (usize >= vsize);
+       }
+
+       if (usize) {
+               if (usize < KARATSUBA_THRESHOLD) {
+                       mpi_limb_t tmp;
+                       if (mpihelp_mul(ctx->tspace, vp, vsize, up, usize, &tmp)
+                           < 0)
+                               return -ENOMEM;
+               } else {
+                       if (!ctx->next) {
+                               ctx->next = kzalloc(sizeof *ctx, GFP_KERNEL);
+                               if (!ctx->next)
+                                       return -ENOMEM;
+                       }
+                       if (mpihelp_mul_karatsuba_case(ctx->tspace,
+                                                      vp, vsize,
+                                                      up, usize,
+                                                      ctx->next) < 0)
+                               return -ENOMEM;
+               }
+
+               cy = mpihelp_add_n(prodp, prodp, ctx->tspace, vsize);
+               mpihelp_add_1(prodp + vsize, ctx->tspace + vsize, usize, cy);
+       }
+
+       return 0;
+}
+
+void mpihelp_release_karatsuba_ctx(struct karatsuba_ctx *ctx)
+{
+       struct karatsuba_ctx *ctx2;
+
+       if (ctx->tp)
+               mpi_free_limb_space(ctx->tp);
+       if (ctx->tspace)
+               mpi_free_limb_space(ctx->tspace);
+       for (ctx = ctx->next; ctx; ctx = ctx2) {
+               ctx2 = ctx->next;
+               if (ctx->tp)
+                       mpi_free_limb_space(ctx->tp);
+               if (ctx->tspace)
+                       mpi_free_limb_space(ctx->tspace);
+               kfree(ctx);
+       }
+}
+
+/* Multiply the natural numbers u (pointed to by UP, with USIZE limbs)
+ * and v (pointed to by VP, with VSIZE limbs), and store the result at
+ * PRODP.  USIZE + VSIZE limbs are always stored, but if the input
+ * operands are normalized.  Return the most significant limb of the
+ * result.
+ *
+ * NOTE: The space pointed to by PRODP is overwritten before finished
+ * with U and V, so overlap is an error.
+ *
+ * Argument constraints:
+ * 1. USIZE >= VSIZE.
+ * 2. PRODP != UP and PRODP != VP, i.e. the destination
+ *    must be distinct from the multiplier and the multiplicand.
+ */
+
+int
+mpihelp_mul(mpi_ptr_t prodp, mpi_ptr_t up, mpi_size_t usize,
+           mpi_ptr_t vp, mpi_size_t vsize, mpi_limb_t *_result)
+{
+       mpi_ptr_t prod_endp = prodp + usize + vsize - 1;
+       mpi_limb_t cy;
+       struct karatsuba_ctx ctx;
+
+       if (vsize < KARATSUBA_THRESHOLD) {
+               mpi_size_t i;
+               mpi_limb_t v_limb;
+
+               if (!vsize) {
+                       *_result = 0;
+                       return 0;
+               }
+
+               /* Multiply by the first limb in V separately, as the result can be
+                * stored (not added) to PROD.  We also avoid a loop for zeroing.  */
+               v_limb = vp[0];
+               if (v_limb <= 1) {
+                       if (v_limb == 1)
+                               MPN_COPY(prodp, up, usize);
+                       else
+                               MPN_ZERO(prodp, usize);
+                       cy = 0;
+               } else
+                       cy = mpihelp_mul_1(prodp, up, usize, v_limb);
+
+               prodp[usize] = cy;
+               prodp++;
+
+               /* For each iteration in the outer loop, multiply one limb from
+                * U with one limb from V, and add it to PROD.  */
+               for (i = 1; i < vsize; i++) {
+                       v_limb = vp[i];
+                       if (v_limb <= 1) {
+                               cy = 0;
+                               if (v_limb == 1)
+                                       cy = mpihelp_add_n(prodp, prodp, up,
+                                                          usize);
+                       } else
+                               cy = mpihelp_addmul_1(prodp, up, usize, v_limb);
+
+                       prodp[usize] = cy;
+                       prodp++;
+               }
+
+               *_result = cy;
+               return 0;
+       }
+
+       memset(&ctx, 0, sizeof ctx);
+       if (mpihelp_mul_karatsuba_case(prodp, up, usize, vp, vsize, &ctx) < 0)
+               return -ENOMEM;
+       mpihelp_release_karatsuba_ctx(&ctx);
+       *_result = *prod_endp;
+       return 0;
+}
diff --git a/lib/mpi/mpiutil.c b/lib/mpi/mpiutil.c
new file mode 100644 (file)
index 0000000..eefc55d
--- /dev/null
@@ -0,0 +1,208 @@
+/* mpiutil.ac  -  Utility functions for MPI
+ * Copyright (C) 1998, 1999 Free Software Foundation, Inc.
+ *
+ * This file is part of GnuPG.
+ *
+ * GnuPG is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation; either version 2 of the License, or
+ * (at your option) any later version.
+ *
+ * GnuPG is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software
+ * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA
+ */
+
+#include "mpi-internal.h"
+
+/****************
+ * Note:  It was a bad idea to use the number of limbs to allocate
+ *       because on a alpha the limbs are large but we normally need
+ *       integers of n bits - So we should chnage this to bits (or bytes).
+ *
+ *       But mpi_alloc is used in a lot of places :-)
+ */
+MPI mpi_alloc(unsigned nlimbs)
+{
+       MPI a;
+
+       a = kmalloc(sizeof *a, GFP_KERNEL);
+       if (!a)
+               return a;
+
+       if (nlimbs) {
+               a->d = mpi_alloc_limb_space(nlimbs);
+               if (!a->d) {
+                       kfree(a);
+                       return NULL;
+               }
+       } else {
+               a->d = NULL;
+       }
+
+       a->alloced = nlimbs;
+       a->nlimbs = 0;
+       a->sign = 0;
+       a->flags = 0;
+       a->nbits = 0;
+       return a;
+}
+EXPORT_SYMBOL_GPL(mpi_alloc);
+
+mpi_ptr_t mpi_alloc_limb_space(unsigned nlimbs)
+{
+       size_t len = nlimbs * sizeof(mpi_limb_t);
+
+       return kmalloc(len, GFP_KERNEL);
+}
+
+void mpi_free_limb_space(mpi_ptr_t a)
+{
+       if (!a)
+               return;
+
+       kfree(a);
+}
+
+void mpi_assign_limb_space(MPI a, mpi_ptr_t ap, unsigned nlimbs)
+{
+       mpi_free_limb_space(a->d);
+       a->d = ap;
+       a->alloced = nlimbs;
+}
+
+/****************
+ * Resize the array of A to NLIMBS. the additional space is cleared
+ * (set to 0) [done by m_realloc()]
+ */
+int mpi_resize(MPI a, unsigned nlimbs)
+{
+       void *p;
+
+       if (nlimbs <= a->alloced)
+               return 0;       /* no need to do it */
+
+       if (a->d) {
+               p = kmalloc(nlimbs * sizeof(mpi_limb_t), GFP_KERNEL);
+               if (!p)
+                       return -ENOMEM;
+               memcpy(p, a->d, a->alloced * sizeof(mpi_limb_t));
+               kfree(a->d);
+               a->d = p;
+       } else {
+               a->d = kzalloc(nlimbs * sizeof(mpi_limb_t), GFP_KERNEL);
+               if (!a->d)
+                       return -ENOMEM;
+       }
+       a->alloced = nlimbs;
+       return 0;
+}
+
+void mpi_clear(MPI a)
+{
+       a->nlimbs = 0;
+       a->nbits = 0;
+       a->flags = 0;
+}
+
+void mpi_free(MPI a)
+{
+       if (!a)
+               return;
+
+       if (a->flags & 4)
+               kfree(a->d);
+       else
+               mpi_free_limb_space(a->d);
+
+       if (a->flags & ~7)
+               pr_info("invalid flag value in mpi\n");
+       kfree(a);
+}
+EXPORT_SYMBOL_GPL(mpi_free);
+
+/****************
+ * Note: This copy function should not interpret the MPI
+ *      but copy it transparently.
+ */
+int mpi_copy(MPI *copied, const MPI a)
+{
+       size_t i;
+       MPI b;
+
+       *copied = MPI_NULL;
+
+       if (a) {
+               b = mpi_alloc(a->nlimbs);
+               if (!b)
+                       return -ENOMEM;
+
+               b->nlimbs = a->nlimbs;
+               b->sign = a->sign;
+               b->flags = a->flags;
+               b->nbits = a->nbits;
+
+               for (i = 0; i < b->nlimbs; i++)
+                       b->d[i] = a->d[i];
+
+               *copied = b;
+       }
+
+       return 0;
+}
+
+int mpi_set(MPI w, const MPI u)
+{
+       mpi_ptr_t wp, up;
+       mpi_size_t usize = u->nlimbs;
+       int usign = u->sign;
+
+       if (RESIZE_IF_NEEDED(w, (size_t) usize) < 0)
+               return -ENOMEM;
+
+       wp = w->d;
+       up = u->d;
+       MPN_COPY(wp, up, usize);
+       w->nlimbs = usize;
+       w->nbits = u->nbits;
+       w->flags = u->flags;
+       w->sign = usign;
+       return 0;
+}
+
+int mpi_set_ui(MPI w, unsigned long u)
+{
+       if (RESIZE_IF_NEEDED(w, 1) < 0)
+               return -ENOMEM;
+       w->d[0] = u;
+       w->nlimbs = u ? 1 : 0;
+       w->sign = 0;
+       w->nbits = 0;
+       w->flags = 0;
+       return 0;
+}
+
+MPI mpi_alloc_set_ui(unsigned long u)
+{
+       MPI w = mpi_alloc(1);
+       if (!w)
+               return w;
+       w->d[0] = u;
+       w->nlimbs = u ? 1 : 0;
+       w->sign = 0;
+       return w;
+}
+
+void mpi_swap(MPI a, MPI b)
+{
+       struct gcry_mpi tmp;
+
+       tmp = *a;
+       *a = *b;
+       *b = tmp;
+}