ghc/runtime/gmp/mpn_mul_classic.c-EXTRA

   1 /* mpn_mul -- Multiply two natural numbers.
   2
   3 Copyright (C) 1991 Free Software Foundation, Inc.
   4
   5 This file is part of the GNU MP Library.
   6
   7 The GNU MP Library is free software; you can redistribute it and/or modify
   8 it under the terms of the GNU General Public License as published by
   9 the Free Software Foundation; either version 1, or (at your option)
  10 any later version.
  11
  12 The GNU MP Library 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 General Public License for more details.
  16
  17 You should have received a copy of the GNU General Public License
  18 along with the GNU MP Library; see the file COPYING.  If not, write to
  19 the Free Software Foundation, 675 Mass Ave, Cambridge, MA 02139, USA.  */
  20
  21 #include "gmp.h"
  22 #include "gmp-impl.h"
  23 #include "longlong.h"
  24
  25 /* Multiply the natural numbers u (pointed to by UP, with USIZE limbs)
  26    and v (pointed to by VP, with VSIZE limbs), and store the result at
  27    PRODP.  USIZE + VSIZE limbs are always stored, but if the input
  28    operands are normalized, the return value will reflect the true
  29    result size (which is either USIZE + VSIZE, or USIZE + VSIZE -1).
  30
  31    NOTE: The space pointed to by PRODP is overwritten before finished
  32    with U and V, so overlap is an error.
  33
  34    Argument constraints:
  35    1. USIZE >= VSIZE.
  36    2. PRODP != UP and PRODP != VP, i.e. the destination
  37       must be distinct from the multiplier and the multiplicand.  */
  38
  39 mp_size_t
  40 mpn_mul_classic (mp_ptr prodp,
  41                   mp_srcptr up, mp_size_t usize,
  42                   mp_srcptr vp, mp_size_t vsize)
  43 {
  44   mp_size_t n;
  45   mp_size_t prod_size;
  46   mp_limb cy;
  47   int i, j;
  48   mp_limb prod_low, prod_high;
  49   mp_limb cy_dig;
  50   mp_limb v_limb, c;
  51
  52   if (vsize == 0)
  53     return 0;
  54
  55   /* Offset UP and PRODP so that the inner loop can be faster.  */
  56   up += usize;
  57   prodp += usize;
  58
  59   /* Multiply by the first limb in V separately, as the result can
  60      be stored (not added) to PROD.  We also avoid a loop for zeroing.  */
  61   v_limb = vp[0];
  62   cy_dig = 0;
  63   j = -usize;
  64   do
  65     {
  66       umul_ppmm (prod_high, prod_low, up[j], v_limb);
  67       add_ssaaaa (cy_dig, prodp[j], prod_high, prod_low, 0, cy_dig);
  68       j++;
  69     }
  70   while (j < 0);
  71
  72   prodp[j] = cy_dig;
  73   prodp++;
  74
  75   /* For each iteration in the outer loop, multiply one limb from
  76      U with one limb from V, and add it to PROD.  */
  77   for (i = 1; i < vsize; i++)
  78     {
  79       v_limb = vp[i];
  80       cy_dig = 0;
  81       j = -usize;
  82
  83       /* Inner loops.  Simulate the carry flag by jumping between
  84          these loops.  The first is used when there was no carry
  85          in the previois iteration; the second when there was carry.  */
  86
  87       do
  88         {
  89           umul_ppmm (prod_high, prod_low, up[j], v_limb);
  90           add_ssaaaa (cy_dig, prod_low, prod_high, prod_low, 0, cy_dig);
  91           c = prodp[j];
  92           prod_low += c;
  93           prodp[j] = prod_low;
  94           if (prod_low < c)
  95             goto cy_loop;
  96         ncy_loop:
  97           j++;
  98         }
  99       while (j < 0);
 100
 101       prodp[j] = cy_dig;
 102       prodp++;
 103       continue;
 104
 105       do
 106         {
 107           umul_ppmm (prod_high, prod_low, up[j], v_limb);
 108           add_ssaaaa (cy_dig, prod_low, prod_high, prod_low, 0, cy_dig);
 109           c = prodp[j];
 110           prod_low += c + 1;
 111           prodp[j] = prod_low;
 112           if (prod_low > c)
 113             goto ncy_loop;
 114         cy_loop:
 115           j++;
 116         }
 117       while (j < 0);
 118
 119       cy_dig += 1;
 120       prodp[j] = cy_dig;
 121       prodp++;
 122     }
 123
 124   return usize + vsize - (cy_dig == 0);
 125 }