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