madd.cpp

   1 // Bignum addition and subtraction
   2
   3 #include "stdafx.h"
   4 #include "defs.h"
   5
   6 static unsigned int *addf(unsigned int *, unsigned int *);
   7 static unsigned int *subf(unsigned int *, unsigned int *);
   8 static int ucmp(unsigned int *, unsigned int *);
   9
  10 unsigned int *
  11 madd(unsigned int *a, unsigned int *b)
  12 {
  13         if (MSIGN(a) == MSIGN(b))
  14                 return addf(a, b);      // same sign, add together
  15         else
  16                 return subf(a, b);      // opposite sign, find difference
  17 }
  18
  19 unsigned int *
  20 msub(unsigned int *a, unsigned int *b)
  21 {
  22         if (MSIGN(a) == MSIGN(b))
  23                 return subf(a, b);      // same sign, find difference
  24         else
  25                 return addf(a, b);      // opposite sign, add together
  26 }
  27
  28 static unsigned int *
  29 addf(unsigned int *a, unsigned int *b)
  30 {
  31         int i, sign;
  32         unsigned int c, *x;
  33
  34         sign = MSIGN(a);
  35
  36         if (MLENGTH(a) < MLENGTH(b)) {
  37                 x = a;
  38                 a = b;
  39                 b = x;
  40         }
  41
  42         x = mnew(MLENGTH(a) + 1);
  43
  44         c = 0;
  45
  46         for (i = 0; i < MLENGTH(b); i++) {
  47                 x[i] = a[i] + b[i] + c;
  48                 if (c)
  49                         if (a[i] >= x[i])
  50                                 c = 1;
  51                         else
  52                                 c = 0;
  53                 else
  54                         if (a[i] > x[i])
  55                                 c = 1;
  56                         else
  57                                 c = 0;
  58         }
  59
  60         for (i = MLENGTH(b); i < MLENGTH(a); i++) {
  61                 x[i] = a[i] + c;
  62                 if (a[i] > x[i])
  63                         c = 1;
  64                 else
  65                         c = 0;
  66         }
  67
  68         x[MLENGTH(a)] = c;
  69
  70         for (i = MLENGTH(a); i > 0; i--)
  71                 if (x[i])
  72                         break;
  73
  74         MLENGTH(x) = i + 1;
  75         MSIGN(x) = sign;
  76
  77         return x;
  78 }
  79
  80 static unsigned int *
  81 subf(unsigned int *a, unsigned int *b)
  82 {
  83         int i, sign = 0;
  84         unsigned int c, *x;
  85
  86         switch (ucmp(a, b)) {
  87
  88         case 0:
  89                 return mint(0);
  90
  91         case 1:
  92                 sign = MSIGN(a);        /* |a| > |b| */
  93                 break;
  94
  95         case -1:
  96                 sign = -MSIGN(a);       /* |a| < |b| */
  97                 x = a;
  98                 a = b;
  99                 b = x;
 100                 break;
 101         }
 102
 103         x = mnew(MLENGTH(a));
 104
 105         c = 0;
 106
 107         for (i = 0; i < MLENGTH(b); i++) {
 108                 x[i] = a[i] - b[i] - c;
 109                 if (c)
 110                         if (a[i] <= x[i])
 111                                 c = 1;
 112                         else
 113                                 c = 0;
 114                 else
 115                         if (a[i] < x[i])
 116                                 c = 1;
 117                         else
 118                                 c = 0;
 119         }
 120
 121         for (i = MLENGTH(b); i < MLENGTH(a); i++) {
 122                 x[i] = a[i] - c;
 123                 if (a[i] < x[i])
 124                         c = 1;
 125                 else
 126                         c = 0;
 127         }
 128
 129         for (i = MLENGTH(a) - 1; i > 0; i--)
 130                 if (x[i])
 131                         break;
 132
 133         MLENGTH(x) = i + 1;
 134         MSIGN(x) = sign;
 135
 136         return x;
 137 }
 138
 139 // unsigned compare
 140
 141 static int
 142 ucmp(unsigned int *a, unsigned int *b)
 143 {
 144         int i;
 145
 146         if (MLENGTH(a) < MLENGTH(b))
 147                 return -1;
 148
 149         if (MLENGTH(a) > MLENGTH(b))
 150                 return 1;
 151
 152         for (i = MLENGTH(a) - 1; i > 0; i--)
 153                 if (a[i] != b[i])
 154                         break;
 155
 156         if (a[i] < b[i])
 157                 return -1;
 158
 159         if (a[i] > b[i])
 160                 return 1;
 161
 162         return 0;
 163 }