ghc/runtime/gmp/mpn_add.c

   1 /* mpn_add -- Add two low-level integers.
   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 2, 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
  24 /* Add ADD1_PTR/ADD1_SIZE and ADD2_PTR/ADD2_SIZE and store the first
  25    ADD1_SIZE words of the result at SUM_PTR.
  26
  27    Return 1 if carry out was generated, return 0 otherwise.
  28
  29    Argument constraint: ADD1_SIZE >= ADD2_SIZE.
  30
  31    The size of SUM can be calculated as ADD1_SIZE + the return value.  */
  32
  33 mp_limb
  34 #ifdef __STDC__
  35 mpn_add (mp_ptr sum_ptr,
  36          mp_srcptr add1_ptr, mp_size add1_size,
  37          mp_srcptr add2_ptr, mp_size add2_size)
  38 #else
  39 mpn_add (sum_ptr, add1_ptr, add1_size, add2_ptr, add2_size)
  40      mp_ptr sum_ptr;
  41      mp_srcptr add1_ptr;
  42      mp_size add1_size;
  43      mp_srcptr add2_ptr;
  44      mp_size add2_size;
  45 #endif
  46 {
  47   mp_limb a1, a2, sum;
  48   mp_size j;
  49
  50   /* The loop counter and index J goes from some negative value to zero.
  51      This way the loops become faster.  Need to offset the base pointers
  52      to take care of the negative indices.  */
  53
  54   j = -add2_size;
  55   if (j == 0)
  56     goto add2_finished;
  57
  58   add1_ptr -= j;
  59   add2_ptr -= j;
  60   sum_ptr -= j;
  61
  62   /* There are two do-loops, marked NON-CARRY LOOP and CARRY LOOP that
  63      jump between each other.  The first loop is for when the previous
  64      addition didn't produce a carry-out; the second is for the
  65      complementary case.  */
  66
  67   /* NON-CARRY LOOP */
  68   do
  69     {
  70       a1 = add1_ptr[j];
  71       a2 = add2_ptr[j];
  72       sum = a1 + a2;
  73       sum_ptr[j] = sum;
  74       if (sum < a2)
  75         goto cy_loop;
  76     ncy_loop:
  77       j++;
  78     }
  79   while (j < 0);
  80
  81   /* We have exhausted ADD2.  Just copy ADD1 to SUM, and return
  82      0 as an indication of no carry-out.  */
  83
  84  add2_finished:
  85   /* Immediate return if the copy would be a no-op.  */
  86   if (sum_ptr == add1_ptr)
  87     return 0;
  88
  89   j = add2_size - add1_size;
  90   add1_ptr -= j;
  91   sum_ptr -= j;
  92
  93   while (j < 0)
  94     {
  95       sum_ptr[j] = add1_ptr[j];
  96       j++;
  97     }
  98   return 0;
  99
 100   /* CARRY LOOP */
 101   do
 102     {
 103       a1 = add1_ptr[j];
 104       a2 = add2_ptr[j];
 105       sum = a1 + a2 + 1;
 106       sum_ptr[j] = sum;
 107       if (sum > a2)
 108         goto ncy_loop;
 109     cy_loop:
 110       j++;
 111     }
 112   while (j < 0);
 113
 114   j = add2_size - add1_size;
 115   add1_ptr -= j;
 116   sum_ptr -= j;
 117
 118   while (j < 0)
 119     {
 120       a1 = add1_ptr[j];
 121       sum = a1 + 1;
 122       sum_ptr[j] = sum;
 123       if (sum > 0)
 124         goto copy_add1;
 125       j++;
 126     }
 127   return 1;
 128
 129  copy_add1:
 130   if (sum_ptr == add1_ptr)
 131     return 0;
 132
 133   j++;
 134   while (j < 0)
 135     {
 136       sum_ptr[j] = add1_ptr[j];
 137       j++;
 138     }
 139
 140   return 0;
 141 }