usr/src/lib/libmp/common/madd.c

   1 /*      Copyright (c) 1984, 1986, 1987, 1988, 1989 AT&T */
   2 /*        All Rights Reserved   */
   3
   4
   5 /*
   6  * Copyright (c) 1980 Regents of the University of California.
   7  * All rights reserved.  The Berkeley software License Agreement
   8  * specifies the terms and conditions for redistribution.
   9  */
  10 /*      Portions Copyright(c) 1988, Sun Microsystems Inc.       */
  11 /*      All Rights Reserved                                     */
  12
  13 /*
  14  * Copyright (c) 1997, by Sun Microsystems, Inc.
  15  * All rights reserved.
  16  */
  17
  18 #ident  "%Z%%M% %I%     %E% SMI"        /* SVr4.0 1.1   */
  19
  20 /* LINTLIBRARY */
  21
  22 #include <mp.h>
  23 #include "libmp.h"
  24 #include <sys/types.h>
  25 #include <stdlib.h>
  26
  27 static void
  28 m_add(MINT *a, MINT *b, MINT *c)
  29 {
  30         int carry, i;
  31         int x;
  32         short *cval;
  33
  34         cval = _mp_xalloc(a->len + 1, "m_add");
  35         carry = 0;
  36         for (i = 0; i < b->len; i++) {
  37                 x = carry + a->val[i] + b->val[i];
  38                 if (x & 0100000) {
  39                         carry = 1;
  40                         cval[i] = (short)(x & 077777);
  41                 } else {
  42                         carry = 0;
  43                         cval[i] = (short)x;
  44                 }
  45         }
  46         for (; i < a->len; i++) {
  47                 x = carry + a->val[i];
  48                 if (x & 0100000) {
  49                         cval[i] = (short)(x & 077777);
  50                 } else {
  51                         carry = 0;
  52                         cval[i] = (short)x;
  53                 }
  54         }
  55         if (carry == 1) {
  56                 cval[i] = 1;
  57                 c->len = i + 1;
  58         } else {
  59                 c->len = a->len;
  60         }
  61         c->val = cval;
  62         if (c->len == 0) {
  63                 free(cval);
  64         }
  65 }
  66
  67 void
  68 mp_madd(MINT *a, MINT *b, MINT *c)
  69 {
  70         MINT x, y;
  71         int sign;
  72
  73         x.len = y.len = 0;
  74         _mp_move(a, &x);
  75         _mp_move(b, &y);
  76         _mp_xfree(c);
  77         sign = 1;
  78         if (x.len >= 0) {
  79                 if (y.len >= 0) {
  80                         if (x.len >= y.len) {
  81                                 m_add(&x, &y, c);
  82                         } else {
  83                                 m_add(&y, &x, c);
  84                         }
  85                 } else {
  86                         y.len = -y.len;
  87                         mp_msub(&x, &y, c);
  88                 }
  89         } else {
  90                 if (y.len <= 0) {
  91                         x.len = -x.len;
  92                         y.len = -y.len;
  93                         sign = -1;
  94                         mp_madd(&x, &y, c);
  95                 } else {
  96                         x.len = -x.len;
  97                         mp_msub(&y, &x, c);
  98                 }
  99         }
 100         c->len = sign * c->len;
 101         _mp_xfree(&x);
 102         _mp_xfree(&y);
 103 }
 104
 105 static void
 106 m_sub(MINT *a, MINT *b, MINT *c)
 107 {
 108         int x, i;
 109         int borrow;
 110         short one;
 111         MINT mone;
 112
 113         one = 1;
 114         mone.len = 1;
 115         mone.val = &one;
 116         c->val = _mp_xalloc(a->len, "m_sub");
 117         borrow = 0;
 118         for (i = 0; i < b->len; i++) {
 119                 x = borrow + a->val[i] - b->val[i];
 120                 if (x & 0100000) {
 121                         borrow = -1;
 122                         c->val[i] = (short)(x & 077777);
 123                 } else {
 124                         borrow = 0;
 125                         c->val[i] = (short)x;
 126                 }
 127         }
 128         for (; i < a->len; i++) {
 129                 x = borrow + a->val[i];
 130                 if (x & 0100000) {
 131                         c->val[i] = (short)(x & 077777);
 132                 } else {
 133                         borrow = 0;
 134                         c->val[i] = (short)x;
 135                 }
 136         }
 137         if (borrow < 0) {
 138                 for (i = 0; i < a->len; i++) {
 139                         c->val[i] ^= 077777;
 140                 }
 141                 c->len = a->len;
 142                 mp_madd(c, &mone, c);
 143         }
 144         for (i = a->len-1; i >= 0; --i) {
 145                 if (c->val[i] > 0) {
 146                         if (borrow == 0) {
 147                                 c->len = i + 1;
 148                         } else {
 149                                 c->len = -i - 1;
 150                         }
 151                         return;
 152                 }
 153         }
 154         free(c->val);
 155 }
 156
 157 void
 158 mp_msub(MINT *a, MINT *b, MINT *c)
 159 {
 160         MINT x, y;
 161         int sign;
 162
 163         x.len = y.len = 0;
 164         _mp_move(a, &x);
 165         _mp_move(b, &y);
 166         _mp_xfree(c);
 167         sign = 1;
 168         if (x.len >= 0) {
 169                 if (y.len >= 0) {
 170                         if (x.len >= y.len) {
 171                                 m_sub(&x, &y, c);
 172                         } else {
 173                                 sign = -1;
 174                                 mp_msub(&y, &x, c);
 175                         }
 176                 } else {
 177                         y.len = -y.len;
 178                         mp_madd(&x, &y, c);
 179                 }
 180         } else {
 181                 if (y.len <= 0) {
 182                         x.len = -x.len;
 183                         y.len = -y.len;
 184                         mp_msub(&y, &x, c);
 185                 } else {
 186                         x.len = -x.len;
 187                         mp_madd(&x, &y, c);
 188                         sign = -1;
 189                 }
 190         }
 191         c->len = sign * c->len;
 192         _mp_xfree(&x);
 193         _mp_xfree(&y);
 194 }