1*0Sstevel@tonic-gate /* Copyright (c) 1984, 1986, 1987, 1988, 1989 AT&T */
2*0Sstevel@tonic-gate /* All Rights Reserved */
3*0Sstevel@tonic-gate
4*0Sstevel@tonic-gate
5*0Sstevel@tonic-gate /*
6*0Sstevel@tonic-gate * Copyright (c) 1980 Regents of the University of California.
7*0Sstevel@tonic-gate * All rights reserved. The Berkeley software License Agreement
8*0Sstevel@tonic-gate * specifies the terms and conditions for redistribution.
9*0Sstevel@tonic-gate */
10*0Sstevel@tonic-gate /* Portions Copyright(c) 1988, Sun Microsystems Inc. */
11*0Sstevel@tonic-gate /* All Rights Reserved */
12*0Sstevel@tonic-gate
13*0Sstevel@tonic-gate /*
14*0Sstevel@tonic-gate * Copyright (c) 1997, by Sun Microsystems, Inc.
15*0Sstevel@tonic-gate * All rights reserved.
16*0Sstevel@tonic-gate */
17*0Sstevel@tonic-gate
18*0Sstevel@tonic-gate #ident "%Z%%M% %I% %E% SMI" /* SVr4.0 1.1 */
19*0Sstevel@tonic-gate
20*0Sstevel@tonic-gate /* LINTLIBRARY */
21*0Sstevel@tonic-gate
22*0Sstevel@tonic-gate #include <mp.h>
23*0Sstevel@tonic-gate #include <sys/types.h>
24*0Sstevel@tonic-gate #include "libmp.h"
25*0Sstevel@tonic-gate
26*0Sstevel@tonic-gate static void m_mult(MINT *, MINT *, MINT *);
27*0Sstevel@tonic-gate
28*0Sstevel@tonic-gate void
mp_mult(MINT * a,MINT * b,MINT * c)29*0Sstevel@tonic-gate mp_mult(MINT *a, MINT *b, MINT *c)
30*0Sstevel@tonic-gate {
31*0Sstevel@tonic-gate struct mint x, y;
32*0Sstevel@tonic-gate int sign;
33*0Sstevel@tonic-gate
34*0Sstevel@tonic-gate _mp_mcan(a);
35*0Sstevel@tonic-gate _mp_mcan(b);
36*0Sstevel@tonic-gate if (a->len == 0 || b->len == 0) {
37*0Sstevel@tonic-gate _mp_xfree(c);
38*0Sstevel@tonic-gate return;
39*0Sstevel@tonic-gate }
40*0Sstevel@tonic-gate sign = 1;
41*0Sstevel@tonic-gate x.len = y.len = 0;
42*0Sstevel@tonic-gate _mp_move(a, &x);
43*0Sstevel@tonic-gate _mp_move(b, &y);
44*0Sstevel@tonic-gate if (a->len < 0) {
45*0Sstevel@tonic-gate x.len = -x.len;
46*0Sstevel@tonic-gate sign = -sign;
47*0Sstevel@tonic-gate }
48*0Sstevel@tonic-gate if (b->len < 0) {
49*0Sstevel@tonic-gate y.len = -y.len;
50*0Sstevel@tonic-gate sign = -sign;
51*0Sstevel@tonic-gate }
52*0Sstevel@tonic-gate _mp_xfree(c);
53*0Sstevel@tonic-gate if (x.len < y.len) {
54*0Sstevel@tonic-gate m_mult(&x, &y, c);
55*0Sstevel@tonic-gate } else {
56*0Sstevel@tonic-gate m_mult(&y, &x, c);
57*0Sstevel@tonic-gate }
58*0Sstevel@tonic-gate if (sign < 0)
59*0Sstevel@tonic-gate c->len = -c->len;
60*0Sstevel@tonic-gate if (c->len == 0)
61*0Sstevel@tonic-gate _mp_xfree(c);
62*0Sstevel@tonic-gate _mp_xfree(&x);
63*0Sstevel@tonic-gate _mp_xfree(&y);
64*0Sstevel@tonic-gate }
65*0Sstevel@tonic-gate
66*0Sstevel@tonic-gate /*
67*0Sstevel@tonic-gate * Knuth 4.3.1, Algorithm M
68*0Sstevel@tonic-gate */
69*0Sstevel@tonic-gate static void
m_mult(MINT * a,MINT * b,MINT * c)70*0Sstevel@tonic-gate m_mult(MINT *a, MINT *b, MINT *c)
71*0Sstevel@tonic-gate {
72*0Sstevel@tonic-gate int i, j;
73*0Sstevel@tonic-gate int sum;
74*0Sstevel@tonic-gate short bcache;
75*0Sstevel@tonic-gate short *aptr;
76*0Sstevel@tonic-gate short *bptr;
77*0Sstevel@tonic-gate short *cptr;
78*0Sstevel@tonic-gate short fifteen = 15;
79*0Sstevel@tonic-gate int alen;
80*0Sstevel@tonic-gate int blen;
81*0Sstevel@tonic-gate
82*0Sstevel@tonic-gate #define BASEBITS (8 * (unsigned int)sizeof (short) - 1)
83*0Sstevel@tonic-gate #define BASE (1 << BASEBITS)
84*0Sstevel@tonic-gate #define LOWBITS (BASE - 1)
85*0Sstevel@tonic-gate
86*0Sstevel@tonic-gate alen = a->len;
87*0Sstevel@tonic-gate blen = b->len;
88*0Sstevel@tonic-gate
89*0Sstevel@tonic-gate c->len = alen + blen;
90*0Sstevel@tonic-gate c->val = _mp_xalloc(c->len, "m_mult");
91*0Sstevel@tonic-gate
92*0Sstevel@tonic-gate aptr = a->val;
93*0Sstevel@tonic-gate bptr = b->val;
94*0Sstevel@tonic-gate cptr = c->val;
95*0Sstevel@tonic-gate
96*0Sstevel@tonic-gate sum = 0;
97*0Sstevel@tonic-gate bcache = *bptr++;
98*0Sstevel@tonic-gate for (i = alen; i > 0; i--) {
99*0Sstevel@tonic-gate sum += *aptr++ * bcache;
100*0Sstevel@tonic-gate *cptr++ = (short)(sum & LOWBITS);
101*0Sstevel@tonic-gate if (sum >= 0)
102*0Sstevel@tonic-gate sum >>= fifteen;
103*0Sstevel@tonic-gate else
104*0Sstevel@tonic-gate sum = 0xfffe0000 | (sum >> fifteen);
105*0Sstevel@tonic-gate }
106*0Sstevel@tonic-gate *cptr = (short)sum;
107*0Sstevel@tonic-gate aptr -= alen;
108*0Sstevel@tonic-gate cptr -= alen;
109*0Sstevel@tonic-gate cptr++;
110*0Sstevel@tonic-gate
111*0Sstevel@tonic-gate for (j = blen - 1; j > 0; j--) {
112*0Sstevel@tonic-gate sum = 0;
113*0Sstevel@tonic-gate bcache = *bptr++;
114*0Sstevel@tonic-gate for (i = alen; i > 0; i--) {
115*0Sstevel@tonic-gate sum += *aptr++ * bcache + *cptr;
116*0Sstevel@tonic-gate *cptr++ = (short)(sum & LOWBITS);
117*0Sstevel@tonic-gate if (sum >= 0)
118*0Sstevel@tonic-gate sum >>= fifteen;
119*0Sstevel@tonic-gate else
120*0Sstevel@tonic-gate sum = 0xfffe0000 | (sum >> fifteen);
121*0Sstevel@tonic-gate }
122*0Sstevel@tonic-gate *cptr = (short)sum;
123*0Sstevel@tonic-gate aptr -= alen;
124*0Sstevel@tonic-gate cptr -= alen;
125*0Sstevel@tonic-gate cptr++;
126*0Sstevel@tonic-gate }
127*0Sstevel@tonic-gate if (c->val[c->len-1] == 0) {
128*0Sstevel@tonic-gate c->len--;
129*0Sstevel@tonic-gate }
130*0Sstevel@tonic-gate }
131