/* Copyright (c) 1984, 1986, 1987, 1988, 1989 AT&T */
/* All Rights Reserved */
/*
* Copyright (c) 1980 Regents of the University of California.
* All rights reserved. The Berkeley software License Agreement
* specifies the terms and conditions for redistribution.
*/
/* Portions Copyright(c) 1988, Sun Microsystems Inc. */
/* All Rights Reserved */
/*
* Copyright (c) 1997, by Sun Microsystems, Inc.
* All rights reserved.
*/
#ident "%Z%%M% %I% %E% SMI" /* SVr4.0 1.1 */
/* LINTLIBRARY */
#include <mp.h>
#include <sys/types.h>
#include "libmp.h"
static void m_mult(MINT *, MINT *, MINT *);
void
mp_mult(MINT *a, MINT *b, MINT *c)
{
struct mint x, y;
int sign;
_mp_mcan(a);
_mp_mcan(b);
if (a->len == 0 || b->len == 0) {
_mp_xfree(c);
return;
}
sign = 1;
x.len = y.len = 0;
_mp_move(a, &x);
_mp_move(b, &y);
if (a->len < 0) {
x.len = -x.len;
sign = -sign;
}
if (b->len < 0) {
y.len = -y.len;
sign = -sign;
}
_mp_xfree(c);
if (x.len < y.len) {
m_mult(&x, &y, c);
} else {
m_mult(&y, &x, c);
}
if (sign < 0)
c->len = -c->len;
if (c->len == 0)
_mp_xfree(c);
_mp_xfree(&x);
_mp_xfree(&y);
}
/*
* Knuth 4.3.1, Algorithm M
*/
static void
m_mult(MINT *a, MINT *b, MINT *c)
{
int i, j;
int sum;
short bcache;
short *aptr;
short *bptr;
short *cptr;
short fifteen = 15;
int alen;
int blen;
#define BASEBITS (8 * (unsigned int)sizeof (short) - 1)
#define BASE (1 << BASEBITS)
#define LOWBITS (BASE - 1)
alen = a->len;
blen = b->len;
c->len = alen + blen;
c->val = _mp_xalloc(c->len, "m_mult");
aptr = a->val;
bptr = b->val;
cptr = c->val;
sum = 0;
bcache = *bptr++;
for (i = alen; i > 0; i--) {
sum += *aptr++ * bcache;
*cptr++ = (short)(sum & LOWBITS);
if (sum >= 0)
sum >>= fifteen;
else
sum = 0xfffe0000 | (sum >> fifteen);
}
*cptr = (short)sum;
aptr -= alen;
cptr -= alen;
cptr++;
for (j = blen - 1; j > 0; j--) {
sum = 0;
bcache = *bptr++;
for (i = alen; i > 0; i--) {
sum += *aptr++ * bcache + *cptr;
*cptr++ = (short)(sum & LOWBITS);
if (sum >= 0)
sum >>= fifteen;
else
sum = 0xfffe0000 | (sum >> fifteen);
}
*cptr = (short)sum;
aptr -= alen;
cptr -= alen;
cptr++;
}
if (c->val[c->len-1] == 0) {
c->len--;
}
}