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
m_add(MINT * a,MINT * b,MINT * c)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
mp_madd(MINT * a,MINT * b,MINT * c)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
m_sub(MINT * a,MINT * b,MINT * c)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
mp_msub(MINT * a,MINT * b,MINT * c)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 }
195