LCOV - code coverage report
Current view: top level - mpi - mpih-mul.c (source / functions) Hit Total Coverage
Test: coverage.info Lines: 128 192 66.7 %
Date: 2016-09-12 12:56:58 Functions: 5 8 62.5 %

          Line data    Source code
       1             : /* mpih-mul.c  -  MPI helper functions
       2             :  * Copyright (C) 1994, 1996, 1998, 1999, 2000,
       3             :  *               2001, 2002 Free Software Foundation, Inc.
       4             :  *
       5             :  * This file is part of Libgcrypt.
       6             :  *
       7             :  * Libgcrypt is free software; you can redistribute it and/or modify
       8             :  * it under the terms of the GNU Lesser General Public License as
       9             :  * published by the Free Software Foundation; either version 2.1 of
      10             :  * the License, or (at your option) any later version.
      11             :  *
      12             :  * Libgcrypt is distributed in the hope that it will be useful,
      13             :  * but WITHOUT ANY WARRANTY; without even the implied warranty of
      14             :  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
      15             :  * GNU Lesser General Public License for more details.
      16             :  *
      17             :  * You should have received a copy of the GNU Lesser General Public
      18             :  * License along with this program; if not, write to the Free Software
      19             :  * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA
      20             :  *
      21             :  * Note: This code is heavily based on the GNU MP Library.
      22             :  *       Actually it's the same code with only minor changes in the
      23             :  *       way the data is stored; this is to support the abstraction
      24             :  *       of an optional secure memory allocation which may be used
      25             :  *       to avoid revealing of sensitive data due to paging etc.
      26             :  */
      27             : 
      28             : #include <config.h>
      29             : #include <stdio.h>
      30             : #include <stdlib.h>
      31             : #include <string.h>
      32             : #include "mpi-internal.h"
      33             : #include "longlong.h"
      34             : #include "g10lib.h"
      35             : 
      36             : #define MPN_MUL_N_RECURSE(prodp, up, vp, size, tspace) \
      37             :     do {                                                \
      38             :         if( (size) < KARATSUBA_THRESHOLD )           \
      39             :             mul_n_basecase (prodp, up, vp, size);       \
      40             :         else                                            \
      41             :             mul_n (prodp, up, vp, size, tspace);        \
      42             :     } while (0);
      43             : 
      44             : #define MPN_SQR_N_RECURSE(prodp, up, size, tspace) \
      45             :     do {                                            \
      46             :         if ((size) < KARATSUBA_THRESHOLD)        \
      47             :             _gcry_mpih_sqr_n_basecase (prodp, up, size);         \
      48             :         else                                        \
      49             :             _gcry_mpih_sqr_n (prodp, up, size, tspace);  \
      50             :     } while (0);
      51             : 
      52             : 
      53             : 
      54             : 
      55             : /* Multiply the natural numbers u (pointed to by UP) and v (pointed to by VP),
      56             :  * both with SIZE limbs, and store the result at PRODP.  2 * SIZE limbs are
      57             :  * always stored.  Return the most significant limb.
      58             :  *
      59             :  * Argument constraints:
      60             :  * 1. PRODP != UP and PRODP != VP, i.e. the destination
      61             :  *    must be distinct from the multiplier and the multiplicand.
      62             :  *
      63             :  *
      64             :  * Handle simple cases with traditional multiplication.
      65             :  *
      66             :  * This is the most critical code of multiplication.  All multiplies rely
      67             :  * on this, both small and huge.  Small ones arrive here immediately.  Huge
      68             :  * ones arrive here as this is the base case for Karatsuba's recursive
      69             :  * algorithm below.
      70             :  */
      71             : 
      72             : static mpi_limb_t
      73    41657037 : mul_n_basecase( mpi_ptr_t prodp, mpi_ptr_t up,
      74             :                                  mpi_ptr_t vp, mpi_size_t size)
      75             : {
      76             :     mpi_size_t i;
      77             :     mpi_limb_t cy;
      78             :     mpi_limb_t v_limb;
      79             : 
      80             :     /* Multiply by the first limb in V separately, as the result can be
      81             :      * stored (not added) to PROD.  We also avoid a loop for zeroing.  */
      82    41657037 :     v_limb = vp[0];
      83    41657037 :     if( v_limb <= 1 ) {
      84      508482 :         if( v_limb == 1 )
      85         260 :             MPN_COPY( prodp, up, size );
      86             :         else
      87      508222 :             MPN_ZERO( prodp, size );
      88      508482 :         cy = 0;
      89             :     }
      90             :     else
      91    41148555 :         cy = _gcry_mpih_mul_1( prodp, up, size, v_limb );
      92             : 
      93    41657037 :     prodp[size] = cy;
      94    41657037 :     prodp++;
      95             : 
      96             :     /* For each iteration in the outer loop, multiply one limb from
      97             :      * U with one limb from V, and add it to PROD.  */
      98   361255137 :     for( i = 1; i < size; i++ ) {
      99   319598100 :         v_limb = vp[i];
     100   319598100 :         if( v_limb <= 1 ) {
     101    10967972 :             cy = 0;
     102    10967972 :             if( v_limb == 1 )
     103        3713 :                cy = _gcry_mpih_add_n(prodp, prodp, up, size);
     104             :         }
     105             :         else
     106   308630128 :             cy = _gcry_mpih_addmul_1(prodp, up, size, v_limb);
     107             : 
     108   319598100 :         prodp[size] = cy;
     109   319598100 :         prodp++;
     110             :     }
     111             : 
     112    41657037 :     return cy;
     113             : }
     114             : 
     115             : 
     116             : static void
     117    17587489 : mul_n( mpi_ptr_t prodp, mpi_ptr_t up, mpi_ptr_t vp,
     118             :                         mpi_size_t size, mpi_ptr_t tspace )
     119             : {
     120    17587489 :     if( size & 1 ) {
     121             :       /* The size is odd, and the code below doesn't handle that.
     122             :        * Multiply the least significant (size - 1) limbs with a recursive
     123             :        * call, and handle the most significant limb of S1 and S2
     124             :        * separately.
     125             :        * A slightly faster way to do this would be to make the Karatsuba
     126             :        * code below behave as if the size were even, and let it check for
     127             :        * odd size in the end.  I.e., in essence move this code to the end.
     128             :        * Doing so would save us a recursive call, and potentially make the
     129             :        * stack grow a lot less.
     130             :        */
     131      681546 :       mpi_size_t esize = size - 1;       /* even size */
     132             :       mpi_limb_t cy_limb;
     133             : 
     134      681546 :       MPN_MUL_N_RECURSE( prodp, up, vp, esize, tspace );
     135      681546 :       cy_limb = _gcry_mpih_addmul_1( prodp + esize, up, esize, vp[esize] );
     136      681546 :       prodp[esize + esize] = cy_limb;
     137      681546 :       cy_limb = _gcry_mpih_addmul_1( prodp + esize, vp, size, up[esize] );
     138      681546 :       prodp[esize + size] = cy_limb;
     139             :     }
     140             :     else {
     141             :         /* Anatolij Alekseevich Karatsuba's divide-and-conquer algorithm.
     142             :          *
     143             :          * Split U in two pieces, U1 and U0, such that
     144             :          * U = U0 + U1*(B**n),
     145             :          * and V in V1 and V0, such that
     146             :          * V = V0 + V1*(B**n).
     147             :          *
     148             :          * UV is then computed recursively using the identity
     149             :          *
     150             :          *        2n   n          n                     n
     151             :          * UV = (B  + B )U V  +  B (U -U )(V -V )  +  (B + 1)U V
     152             :          *                1 1        1  0   0  1              0 0
     153             :          *
     154             :          * Where B = 2**BITS_PER_MP_LIMB.
     155             :          */
     156    16905943 :         mpi_size_t hsize = size >> 1;
     157             :         mpi_limb_t cy;
     158             :         int negflg;
     159             : 
     160             :         /* Product H.      ________________  ________________
     161             :          *                |_____U1 x V1____||____U0 x V0_____|
     162             :          * Put result in upper part of PROD and pass low part of TSPACE
     163             :          * as new TSPACE.
     164             :          */
     165    16905943 :         MPN_MUL_N_RECURSE(prodp + size, up + hsize, vp + hsize, hsize, tspace);
     166             : 
     167             :         /* Product M.      ________________
     168             :          *                |_(U1-U0)(V0-V1)_|
     169             :          */
     170    16905943 :         if( _gcry_mpih_cmp(up + hsize, up, hsize) >= 0 ) {
     171     6666260 :             _gcry_mpih_sub_n(prodp, up + hsize, up, hsize);
     172     6666260 :             negflg = 0;
     173             :         }
     174             :         else {
     175    10239683 :             _gcry_mpih_sub_n(prodp, up, up + hsize, hsize);
     176    10239683 :             negflg = 1;
     177             :         }
     178    16905943 :         if( _gcry_mpih_cmp(vp + hsize, vp, hsize) >= 0 ) {
     179     6509968 :             _gcry_mpih_sub_n(prodp + hsize, vp + hsize, vp, hsize);
     180     6509968 :             negflg ^= 1;
     181             :         }
     182             :         else {
     183    10395975 :             _gcry_mpih_sub_n(prodp + hsize, vp, vp + hsize, hsize);
     184             :             /* No change of NEGFLG.  */
     185             :         }
     186             :         /* Read temporary operands from low part of PROD.
     187             :          * Put result in low part of TSPACE using upper part of TSPACE
     188             :          * as new TSPACE.
     189             :          */
     190    16905943 :         MPN_MUL_N_RECURSE(tspace, prodp, prodp + hsize, hsize, tspace + size);
     191             : 
     192             :         /* Add/copy product H. */
     193    16905943 :         MPN_COPY (prodp + hsize, prodp + size, hsize);
     194    16905943 :         cy = _gcry_mpih_add_n( prodp + size, prodp + size,
     195    16905943 :                             prodp + size + hsize, hsize);
     196             : 
     197             :         /* Add product M (if NEGFLG M is a negative number) */
     198    16905943 :         if(negflg)
     199    16274885 :             cy -= _gcry_mpih_sub_n(prodp + hsize, prodp + hsize, tspace, size);
     200             :         else
     201      631058 :             cy += _gcry_mpih_add_n(prodp + hsize, prodp + hsize, tspace, size);
     202             : 
     203             :         /* Product L.      ________________  ________________
     204             :          *                |________________||____U0 x V0_____|
     205             :          * Read temporary operands from low part of PROD.
     206             :          * Put result in low part of TSPACE using upper part of TSPACE
     207             :          * as new TSPACE.
     208             :          */
     209    16905943 :         MPN_MUL_N_RECURSE(tspace, up, vp, hsize, tspace + size);
     210             : 
     211             :         /* Add/copy Product L (twice) */
     212             : 
     213    16905943 :         cy += _gcry_mpih_add_n(prodp + hsize, prodp + hsize, tspace, size);
     214    16905943 :         if( cy )
     215     6151022 :           _gcry_mpih_add_1(prodp + hsize + size, prodp + hsize + size, hsize, cy);
     216             : 
     217    16905943 :         MPN_COPY(prodp, tspace, hsize);
     218    16905943 :         cy = _gcry_mpih_add_n(prodp + hsize, prodp + hsize, tspace + hsize, hsize);
     219    16905943 :         if( cy )
     220     5403784 :             _gcry_mpih_add_1(prodp + size, prodp + size, size, 1);
     221             :     }
     222    17587489 : }
     223             : 
     224             : 
     225             : void
     226           0 : _gcry_mpih_sqr_n_basecase( mpi_ptr_t prodp, mpi_ptr_t up, mpi_size_t size )
     227             : {
     228             :     mpi_size_t i;
     229             :     mpi_limb_t cy_limb;
     230             :     mpi_limb_t v_limb;
     231             : 
     232             :     /* Multiply by the first limb in V separately, as the result can be
     233             :      * stored (not added) to PROD.  We also avoid a loop for zeroing.  */
     234           0 :     v_limb = up[0];
     235           0 :     if( v_limb <= 1 ) {
     236           0 :         if( v_limb == 1 )
     237           0 :             MPN_COPY( prodp, up, size );
     238             :         else
     239           0 :             MPN_ZERO(prodp, size);
     240           0 :         cy_limb = 0;
     241             :     }
     242             :     else
     243           0 :         cy_limb = _gcry_mpih_mul_1( prodp, up, size, v_limb );
     244             : 
     245           0 :     prodp[size] = cy_limb;
     246           0 :     prodp++;
     247             : 
     248             :     /* For each iteration in the outer loop, multiply one limb from
     249             :      * U with one limb from V, and add it to PROD.  */
     250           0 :     for( i=1; i < size; i++) {
     251           0 :         v_limb = up[i];
     252           0 :         if( v_limb <= 1 ) {
     253           0 :             cy_limb = 0;
     254           0 :             if( v_limb == 1 )
     255           0 :                 cy_limb = _gcry_mpih_add_n(prodp, prodp, up, size);
     256             :         }
     257             :         else
     258           0 :             cy_limb = _gcry_mpih_addmul_1(prodp, up, size, v_limb);
     259             : 
     260           0 :         prodp[size] = cy_limb;
     261           0 :         prodp++;
     262             :     }
     263           0 : }
     264             : 
     265             : 
     266             : void
     267           0 : _gcry_mpih_sqr_n( mpi_ptr_t prodp,
     268             :                   mpi_ptr_t up, mpi_size_t size, mpi_ptr_t tspace)
     269             : {
     270           0 :     if( size & 1 ) {
     271             :         /* The size is odd, and the code below doesn't handle that.
     272             :          * Multiply the least significant (size - 1) limbs with a recursive
     273             :          * call, and handle the most significant limb of S1 and S2
     274             :          * separately.
     275             :          * A slightly faster way to do this would be to make the Karatsuba
     276             :          * code below behave as if the size were even, and let it check for
     277             :          * odd size in the end.  I.e., in essence move this code to the end.
     278             :          * Doing so would save us a recursive call, and potentially make the
     279             :          * stack grow a lot less.
     280             :          */
     281           0 :         mpi_size_t esize = size - 1;       /* even size */
     282             :         mpi_limb_t cy_limb;
     283             : 
     284           0 :         MPN_SQR_N_RECURSE( prodp, up, esize, tspace );
     285           0 :         cy_limb = _gcry_mpih_addmul_1( prodp + esize, up, esize, up[esize] );
     286           0 :         prodp[esize + esize] = cy_limb;
     287           0 :         cy_limb = _gcry_mpih_addmul_1( prodp + esize, up, size, up[esize] );
     288             : 
     289           0 :         prodp[esize + size] = cy_limb;
     290             :     }
     291             :     else {
     292           0 :         mpi_size_t hsize = size >> 1;
     293             :         mpi_limb_t cy;
     294             : 
     295             :         /* Product H.      ________________  ________________
     296             :          *                |_____U1 x U1____||____U0 x U0_____|
     297             :          * Put result in upper part of PROD and pass low part of TSPACE
     298             :          * as new TSPACE.
     299             :          */
     300           0 :         MPN_SQR_N_RECURSE(prodp + size, up + hsize, hsize, tspace);
     301             : 
     302             :         /* Product M.      ________________
     303             :          *                |_(U1-U0)(U0-U1)_|
     304             :          */
     305           0 :         if( _gcry_mpih_cmp( up + hsize, up, hsize) >= 0 )
     306           0 :             _gcry_mpih_sub_n( prodp, up + hsize, up, hsize);
     307             :         else
     308           0 :             _gcry_mpih_sub_n (prodp, up, up + hsize, hsize);
     309             : 
     310             :         /* Read temporary operands from low part of PROD.
     311             :          * Put result in low part of TSPACE using upper part of TSPACE
     312             :          * as new TSPACE.  */
     313           0 :         MPN_SQR_N_RECURSE(tspace, prodp, hsize, tspace + size);
     314             : 
     315             :         /* Add/copy product H  */
     316           0 :         MPN_COPY(prodp + hsize, prodp + size, hsize);
     317           0 :         cy = _gcry_mpih_add_n(prodp + size, prodp + size,
     318           0 :                            prodp + size + hsize, hsize);
     319             : 
     320             :         /* Add product M (if NEGFLG M is a negative number).  */
     321           0 :         cy -= _gcry_mpih_sub_n (prodp + hsize, prodp + hsize, tspace, size);
     322             : 
     323             :         /* Product L.      ________________  ________________
     324             :          *                |________________||____U0 x U0_____|
     325             :          * Read temporary operands from low part of PROD.
     326             :          * Put result in low part of TSPACE using upper part of TSPACE
     327             :          * as new TSPACE.  */
     328           0 :         MPN_SQR_N_RECURSE (tspace, up, hsize, tspace + size);
     329             : 
     330             :         /* Add/copy Product L (twice).  */
     331           0 :         cy += _gcry_mpih_add_n (prodp + hsize, prodp + hsize, tspace, size);
     332           0 :         if( cy )
     333           0 :             _gcry_mpih_add_1(prodp + hsize + size, prodp + hsize + size,
     334             :                                                             hsize, cy);
     335             : 
     336           0 :         MPN_COPY(prodp, tspace, hsize);
     337           0 :         cy = _gcry_mpih_add_n (prodp + hsize, prodp + hsize, tspace + hsize, hsize);
     338           0 :         if( cy )
     339           0 :             _gcry_mpih_add_1 (prodp + size, prodp + size, size, 1);
     340             :     }
     341           0 : }
     342             : 
     343             : 
     344             : /* This should be made into an inline function in gmp.h.  */
     345             : void
     346           0 : _gcry_mpih_mul_n( mpi_ptr_t prodp,
     347             :                      mpi_ptr_t up, mpi_ptr_t vp, mpi_size_t size)
     348             : {
     349             :     int secure;
     350             : 
     351           0 :     if( up == vp ) {
     352           0 :         if( size < KARATSUBA_THRESHOLD )
     353           0 :             _gcry_mpih_sqr_n_basecase( prodp, up, size );
     354             :         else {
     355             :             mpi_ptr_t tspace;
     356           0 :             secure = _gcry_is_secure( up );
     357           0 :             tspace = mpi_alloc_limb_space( 2 * size, secure );
     358           0 :             _gcry_mpih_sqr_n( prodp, up, size, tspace );
     359           0 :             _gcry_mpi_free_limb_space (tspace, 2 * size );
     360             :         }
     361             :     }
     362             :     else {
     363           0 :         if( size < KARATSUBA_THRESHOLD )
     364           0 :             mul_n_basecase( prodp, up, vp, size );
     365             :         else {
     366             :             mpi_ptr_t tspace;
     367           0 :             secure = _gcry_is_secure( up ) || _gcry_is_secure( vp );
     368           0 :             tspace = mpi_alloc_limb_space( 2 * size, secure );
     369           0 :             mul_n (prodp, up, vp, size, tspace);
     370           0 :             _gcry_mpi_free_limb_space (tspace, 2 * size );
     371             :         }
     372             :     }
     373           0 : }
     374             : 
     375             : 
     376             : 
     377             : void
     378     7821503 : _gcry_mpih_mul_karatsuba_case( mpi_ptr_t prodp,
     379             :                                   mpi_ptr_t up, mpi_size_t usize,
     380             :                                   mpi_ptr_t vp, mpi_size_t vsize,
     381             :                                   struct karatsuba_ctx *ctx )
     382             : {
     383             :     mpi_limb_t cy;
     384             : 
     385     7821503 :     if( !ctx->tspace || ctx->tspace_size < vsize ) {
     386       71123 :         if( ctx->tspace )
     387         625 :             _gcry_mpi_free_limb_space( ctx->tspace, ctx->tspace_nlimbs );
     388       71123 :         ctx->tspace_nlimbs = 2 * vsize;
     389       71123 :         ctx->tspace = mpi_alloc_limb_space (2 * vsize,
     390             :                                             (_gcry_is_secure (up)
     391             :                                              || _gcry_is_secure (vp)));
     392       71123 :         ctx->tspace_size = vsize;
     393             :     }
     394             : 
     395     7821503 :     MPN_MUL_N_RECURSE( prodp, up, vp, vsize, ctx->tspace );
     396             : 
     397     7821503 :     prodp += vsize;
     398     7821503 :     up += vsize;
     399     7821503 :     usize -= vsize;
     400     7821503 :     if( usize >= vsize ) {
     401       23648 :         if( !ctx->tp || ctx->tp_size < vsize ) {
     402         387 :             if( ctx->tp )
     403         203 :                 _gcry_mpi_free_limb_space( ctx->tp, ctx->tp_nlimbs );
     404         387 :             ctx->tp_nlimbs = 2 * vsize;
     405         387 :             ctx->tp = mpi_alloc_limb_space (2 * vsize,
     406             :                                             (_gcry_is_secure (up)
     407             :                                              || _gcry_is_secure (vp)));
     408         387 :             ctx->tp_size = vsize;
     409             :         }
     410             : 
     411             :         do {
     412       23648 :             MPN_MUL_N_RECURSE( ctx->tp, up, vp, vsize, ctx->tspace );
     413       23648 :             cy = _gcry_mpih_add_n( prodp, prodp, ctx->tp, vsize );
     414       23648 :             _gcry_mpih_add_1( prodp + vsize, ctx->tp + vsize, vsize, cy );
     415       23648 :             prodp += vsize;
     416       23648 :             up += vsize;
     417       23648 :             usize -= vsize;
     418       23648 :         } while( usize >= vsize );
     419             :     }
     420             : 
     421     7821503 :     if( usize ) {
     422      204278 :         if( usize < KARATSUBA_THRESHOLD ) {
     423      180743 :             _gcry_mpih_mul( ctx->tspace, vp, vsize, up, usize );
     424             :         }
     425             :         else {
     426       23535 :             if( !ctx->next ) {
     427         184 :                 ctx->next = xcalloc( 1, sizeof *ctx );
     428             :             }
     429       23535 :             _gcry_mpih_mul_karatsuba_case( ctx->tspace,
     430             :                                         vp, vsize,
     431             :                                         up, usize,
     432             :                                         ctx->next );
     433             :         }
     434             : 
     435      204278 :         cy = _gcry_mpih_add_n( prodp, prodp, ctx->tspace, vsize);
     436      204278 :         _gcry_mpih_add_1( prodp + vsize, ctx->tspace + vsize, usize, cy );
     437             :     }
     438     7821503 : }
     439             : 
     440             : 
     441             : void
     442      355396 : _gcry_mpih_release_karatsuba_ctx( struct karatsuba_ctx *ctx )
     443             : {
     444             :     struct karatsuba_ctx *ctx2;
     445             : 
     446      355396 :     if( ctx->tp )
     447         184 :         _gcry_mpi_free_limb_space( ctx->tp, ctx->tp_nlimbs );
     448      355396 :     if( ctx->tspace )
     449       70314 :         _gcry_mpi_free_limb_space( ctx->tspace, ctx->tspace_nlimbs );
     450      355580 :     for( ctx=ctx->next; ctx; ctx = ctx2 ) {
     451         184 :         ctx2 = ctx->next;
     452         184 :         if( ctx->tp )
     453           0 :             _gcry_mpi_free_limb_space( ctx->tp, ctx->tp_nlimbs );
     454         184 :         if( ctx->tspace )
     455         184 :             _gcry_mpi_free_limb_space( ctx->tspace, ctx->tspace_nlimbs );
     456         184 :         xfree( ctx );
     457             :     }
     458      355396 : }
     459             : 
     460             : /* Multiply the natural numbers u (pointed to by UP, with USIZE limbs)
     461             :  * and v (pointed to by VP, with VSIZE limbs), and store the result at
     462             :  * PRODP.  USIZE + VSIZE limbs are always stored, but if the input
     463             :  * operands are normalized.  Return the most significant limb of the
     464             :  * result.
     465             :  *
     466             :  * NOTE: The space pointed to by PRODP is overwritten before finished
     467             :  * with U and V, so overlap is an error.
     468             :  *
     469             :  * Argument constraints:
     470             :  * 1. USIZE >= VSIZE.
     471             :  * 2. PRODP != UP and PRODP != VP, i.e. the destination
     472             :  *    must be distinct from the multiplier and the multiplicand.
     473             :  */
     474             : 
     475             : mpi_limb_t
     476    33278126 : _gcry_mpih_mul( mpi_ptr_t prodp, mpi_ptr_t up, mpi_size_t usize,
     477             :                    mpi_ptr_t vp, mpi_size_t vsize)
     478             : {
     479    33278126 :     mpi_ptr_t prod_endp = prodp + usize + vsize - 1;
     480             :     mpi_limb_t cy;
     481             :     struct karatsuba_ctx ctx;
     482             : 
     483    33278126 :     if( vsize < KARATSUBA_THRESHOLD ) {
     484             :         mpi_size_t i;
     485             :         mpi_limb_t v_limb;
     486             : 
     487    33218692 :         if( !vsize )
     488           0 :             return 0;
     489             : 
     490             :         /* Multiply by the first limb in V separately, as the result can be
     491             :          * stored (not added) to PROD.  We also avoid a loop for zeroing.  */
     492    33218692 :         v_limb = vp[0];
     493    33218692 :         if( v_limb <= 1 ) {
     494     1380072 :             if( v_limb == 1 )
     495     1294036 :                 MPN_COPY( prodp, up, usize );
     496             :             else
     497       86036 :                 MPN_ZERO( prodp, usize );
     498     1380072 :             cy = 0;
     499             :         }
     500             :         else
     501    31838620 :             cy = _gcry_mpih_mul_1( prodp, up, usize, v_limb );
     502             : 
     503    33218692 :         prodp[usize] = cy;
     504    33218692 :         prodp++;
     505             : 
     506             :         /* For each iteration in the outer loop, multiply one limb from
     507             :          * U with one limb from V, and add it to PROD.  */
     508   140314615 :         for( i = 1; i < vsize; i++ ) {
     509   107095923 :             v_limb = vp[i];
     510   107095923 :             if( v_limb <= 1 ) {
     511     4350937 :                 cy = 0;
     512     4350937 :                 if( v_limb == 1 )
     513        2977 :                    cy = _gcry_mpih_add_n(prodp, prodp, up, usize);
     514             :             }
     515             :             else
     516   102744986 :                 cy = _gcry_mpih_addmul_1(prodp, up, usize, v_limb);
     517             : 
     518   107095923 :             prodp[usize] = cy;
     519   107095923 :             prodp++;
     520             :         }
     521             : 
     522    33218692 :         return cy;
     523             :     }
     524             : 
     525       59434 :     memset( &ctx, 0, sizeof ctx );
     526       59434 :     _gcry_mpih_mul_karatsuba_case( prodp, up, usize, vp, vsize, &ctx );
     527       59434 :     _gcry_mpih_release_karatsuba_ctx( &ctx );
     528       59434 :     return *prod_endp;
     529             : }

Generated by: LCOV version 1.11